#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
struct cell
{
long long int a,b,mi,ma;
};
struct line
{
long double a,b;
int ind;
};
bool cmp(cell a1,cell a2)
{
if(a1.a!=a2.a)return a1.a<a2.a;
return a1.b>a2.b;
}
long double get_value(line a,long long int x)
{
return a.a*x+a.b;
}
long double intersect(line a1,line a2)
{
if(a1.a==a2.a)
{
cout<<"!!!!!!!!!!!!"<<a1.a<<" "<<a2.a<<endl;
exit(0);
}
return (a1.b-a2.b)/(a2.a-a1.a);
}
cell g[100005];
long long int n,m,k,dp[100005],use[100005],br;
cell c[100005];
vector<line>v;
void clea()
{
int to=-1;
for(int i=1;i<=n;i++)
{
if(to<max(g[i].a,g[i].b))
{
to=max(g[i].a,g[i].b);
br++;
c[br]=g[i];
}
}
}
void add(line c)
{
line top;
while(v.size()>=2)
{
top=v.back();
v.pop_back();
if(intersect(v.back(),top)<intersect(v.back(),c))
{
v.push_back(top);
break;
}
}
v.push_back(c);
}
void make_dp(long long int cost)
{
v.clear();
int to=0;
line g;
add({c[1].mi*-2,c[1].mi*c[1].mi-2*c[1].mi+1,0});
for(int i=1;i<=br;i++)
{
while(to<v.size()-1&&get_value(v[to],c[i].ma)>=get_value(v[to+1],c[i].ma))to++;
dp[i]=v[to].b+v[to].a*c[i].ma+c[i].ma*c[i].ma+2*c[i].ma+cost;
//cout<<v[to].a<<" "<<v[to].b<<" "<<dp[i]<<endl;
use[i]=use[v[to].ind]+1;
if(i==br)break;
g.b=dp[i]+c[i+1].mi*c[i+1].mi-2*c[i+1].mi+1-max(0ll,c[i].ma-c[i+1].mi+1)*max(0ll,c[i].ma-c[i+1].mi+1);
g.a=-2*c[i+1].mi;
g.ind=i;
add(g);
}
}
long long int take_photos(int N, int M, int K, vector<int> R, vector<int> C)
{
n=N;
m=M;
k=K;
for(int i=1;i<=n;i++)
{
g[i].a=R[i-1];
g[i].b=C[i-1];
g[i].mi=min(g[i].a,g[i].b);
g[i].ma=max(g[i].a,g[i].b);
}
sort(g+1,g+n+1,cmp);
clea();
make_dp(0);
return dp[br];
k=min(k,br);
long long int l=1,r=1e12,mid;
while(l<=r)
{
mid=(l+r)/2;
make_dp(mid);
if(use[br]>=k)l=mid+1;
else r=mid-1;
}
//cout<<endl<<endl;
make_dp(l);
//cout<<endl;
//cout<<l<<" "<<use[br]<<" "<<dp[br]<<endl;
return dp[br]-k*l;
}
