#include <bits/stdc++.h>
#include "aliens.h"
#define DIMN 100010
#define INF 2000000000000000000
using namespace std;
pair <long long,long long> v[DIMN];
long long dp[DIMN] , dp2[4010][4010];
long long cnt[DIMN] , tt2[4010][4010] , tt[DIMN];
struct lichao{
long long x , y , nr;
} aint[4000010];
int cmp (pair <long long,long long> x , pair <long long,long long> y){
if (x.first != y.first)
return x.first < y.first;
return x.second > y.second;
}
void update (long long nod,long long st,long long dr,long long x,long long y , long long nr){
if (st == dr){
if (aint[nod].x * st + aint[nod].y > x * st + y){
aint[nod].x = x;
aint[nod].y = y;
aint[nod].nr = nr;
}
return;
}
long long mid = (st+dr)/2,st1=0,st2=0;
if (aint[nod].x * mid + aint[nod].y > x * mid + y)
st1 = 1;
if (aint[nod].x * dr + aint[nod].y > x * dr + y)
st2 = 1;
if (!st1 && !st2){
update (2*nod,st,mid,x,y , nr);
}
else if (!st1 && st2) {
update (2*nod+1,mid+1,dr,x,y , nr);
}
else if (st1 && !st2){
swap(x,aint[nod].x);
swap(y,aint[nod].y);
swap(nr , aint[nod].nr);
update (2*nod+1,mid+1,dr,x,y , nr);
}
else if (st1 && st2){
swap(x,aint[nod].x);
swap(y,aint[nod].y);
swap(nr , aint[nod].nr);
update (2*nod,st,mid,x,y , nr);
}
}
pair <long long , long long> query (long long nod,long long st,long long dr,long long x){
if (st==dr){
return make_pair( aint[nod].x * x + aint[nod].y , 1 + aint[nod].nr);
}
long long mid = (st+dr)/2;
pair <long long , long long> sol = make_pair(INF , 0);
if (x<=mid)
sol = query(2*nod,st,mid,x);
else sol = query(2*nod+1,mid+1,dr,x);
if (sol.first < aint[nod].x * x + aint[nod].y || (sol.first == aint[nod].x * x + aint[nod].y && sol.second < aint[nod].nr + 1))
return sol;
else{
sol = make_pair(aint[nod].x * x + aint[nod].y , 1 + aint[nod].nr);
return sol;
}
}
void build (long long nod,long long st,long long dr){
int mid = (st + dr)/2;
aint[nod].x = aint[nod].y = 1000000000000;
if (st == dr)
return;
build (2*nod,st,mid);
build (2*nod+1,mid+1,dr);
}
pair <long long,long long> solve (long long x , long long n , long long m){ /// cost x , n intervale
long long i , aux;
pair <long long , long long> p;
build (1, 1, m);
//if (x == 0)
// printf ("a");
for (i = 1 ; i <= n ; i++){
aux = max (0LL , (v[i-1].second - v[i].first + 1));
//if (x == 0)
//printf ("%lld %lld\n" , -2 * v[i].first , dp[i-1] + v[i].first * (v[i].first - 2) - aux * aux);
update(1 , 1 , m ,-2 * v[i].first , dp[i-1] + v[i].first * (v[i].first - 2) - aux * aux , cnt[i-1]);
p = query(1 , 1 , m , v[i].second); /// VREAU MINIMUL DE AICI , merge cu li chao??
dp[i] = p.first + v[i].second * v[i].second + 2 * 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;
long long 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);
}
sort (v + 1 , v + n + 1 , cmp);
n2 = 0;
rm = 0;
for (i=1;i<=n;i++){ /// nu iau intervale incluse total unul in altul
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)/2;
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;
}
