#include <bits/stdc++.h>
#include "aliens.h"
#define DIMN 100010
#define INF 2000000000000000000
using namespace std;
pair <int,int> v[DIMN];
long long dp[DIMN];
int cnt[DIMN];
struct lichao{
long long x , y , last;
int nr;
} aint[4000010];
void update (int nod,int st,int dr,long long x,long long y , int nr , long long last){
if (st == dr){
if (1LL * aint[nod].x * st + aint[nod].y > 1LL * x * st + y || aint[nod].last != last){
aint[nod].x = x;
aint[nod].y = y;
aint[nod].nr = nr;
aint[nod].last = last;
}
return;
}
long long mid = ((st + dr) >> 1),st1=0,st2=0;
if (1LL * aint[nod].x * mid + aint[nod].y > 1LL * x * mid + y || aint[nod].last != last)
st1 = 1;
if (1LL * aint[nod].x * dr + aint[nod].y > 1LL * x * dr + y || aint[nod].last != last)
st2 = 1;
if (!st1 && !st2){
update ((nod << 1),st,mid,x,y , nr , last);
}
else if (!st1 && st2) {
update (((nod << 1) | 1),mid+1,dr,x,y , nr , last);
}
else if (st1 && !st2){
swap(x,aint[nod].x);
swap(y,aint[nod].y);
swap(nr , aint[nod].nr);
swap(last , aint[nod].last);
update (((nod << 1) | 1),mid+1,dr,x,y , nr , last);
}
else if (st1 && st2){
swap(x,aint[nod].x);
swap(y,aint[nod].y);
swap(nr , aint[nod].nr);
swap(last , aint[nod].last);
update ((nod << 1),st,mid,x,y , nr , last);
}
}
pair <long long , int> query (long long nod,long long st,long long dr,int x , long long last){
if (st==dr){
if (aint[nod].last == last)
return make_pair( 1LL * aint[nod].x * x + aint[nod].y , 1 + aint[nod].nr);
else return make_pair(INF , 1);
}
long long mid = ((st + dr) >> 1);
pair <long long , int> sol = make_pair(INF , 0);
if (x<=mid)
sol = query((nod << 1),st,mid,x , last);
else sol = query(((nod << 1) | 1),mid+1,dr,x , last);
if (aint[nod].last != last || (sol.first < 1LL * aint[nod].x * x + aint[nod].y || (sol.first == 1LL * aint[nod].x * x + aint[nod].y && sol.second < aint[nod].nr + 1)))
return sol;
else{
if (aint[nod].last == last)
sol = make_pair(1LL * aint[nod].x * x + aint[nod].y , 1 + aint[nod].nr);
return sol;
}
}
pair <long long,long long> solve (long long x , int n , int m){ /// cost x , n intervale
long long i , aux;
pair <long long , long long> p;
/// daca last != x , te prefaci ca valoarea e mai mare
for (i = 1 ; i <= n ; i++){
aux = max (0LL , ((long long)v[i-1].second - v[i].first + 1));
update(1 , 1 , m ,-2LL * v[i].first , dp[i-1] + 1LL * v[i].first * (v[i].first - 2) - 1LL * aux * aux , cnt[i-1] , x);
p = query(1 , 1 , m , v[i].second , x); /// VREAU MINIMUL DE AICI , merge cu li chao??
dp[i] = p.first + 1LL * v[i].second * v[i].second + 2LL * v[i].second + x + 1;
cnt[i] = p.second;
}
return make_pair(cnt[n] , dp[n]);
}
long long take_photos (int n , int m , int k , vector <int> r , vector <int> c){
long long st , dr , mid;
int i , n2 , rm;
pair <long long,long long> rez;
for (i=0;i<n;i++){
v[i+1] = make_pair(r[i] + 1 , c[i] + 1);
if (v[i+1].first > v[i+1].second)
swap (v[i+1].first , v[i+1].second);
v[i+1].second = -v[i+1].second;
}
sort (v + 1 , v + n + 1);
n2 = 0;
rm = 0;
for (i=1;i<=n;i++){ /// nu iau intervale incluse total unul in altul
v[i].second = -v[i].second;
if (rm < v[i].second)
v[++n2] = v[i];
rm = max(rm , v[i].second);
}
n = n2;
if (n <= k)
return solve (0 , n2 , m).second;
st = 0;
dr = 1152921504606846976;
while (st <= dr){
mid = ((st + dr) >> 1);
rez = solve(mid , n2 , m);
if (rez.first > k)
st = mid + 1;
else
dr = mid - 1;
}
rez = solve(st , n2 , m);
return rez.second - st * k;
}
