#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
struct lichao
{
int l, r, k;
long long A, B;
lichao() : l(0), r(0), k(0), A(0), B(0x7fffffffffffffffLL) {}
};
vector<lichao> tree;
vector<pair<int,int>> P;
int get_sign(long long a)
{
return a<0 ? -1:a>0;
}
void update(long long A, long long B, int k, int p=1, int s=0, int e=1000000)
{
int m=(s+e)>>1, &pk=tree[p].k;
long long &pA=tree[p].A, &pB=tree[p].B;
if(pA*m+pB>A*m+B || pA*m+pB==A*m+B && pA*s+pB<A*s+B) {
swap(A,pA);
swap(B,pB);
swap(k,pk);
}
if(pA*s+pB<=A*s+B && pA*e+pB<=A*e+B) return;
if(get_sign(pA*s+pB-(A*s+B))*get_sign(pA*m+pB-(A*m+B))<=0) {
if(tree[p].l==0) tree[p].l=tree.size(), tree.push_back(lichao());
update(A,B,k,tree[p].l,s,m);
}
else {
if(tree[p].r==0) tree[p].r=tree.size(), tree.push_back(lichao());
update(A,B,k,tree[p].r,m+1,e);
}
}
pair<long long,int> query(int x, int p=1, int s=0, int e=1000000)
{
int m=(s+e)>>1;
if(p==0) return {0x7fffffffffffffffLL,0x7fffffff};
return min(make_pair(tree[p].A*x+tree[p].B,tree[p].k),x<=m ? query(x,tree[p].l,s,m):query(x,tree[p].r,m+1,e));
}
pair<long long,int> solve(long long l)
{
int N=P.size()-1;
pair<long long,int> ret;
tree.resize(2);
tree[1]=lichao();
update(-2LL*P[0].first,1LL*P[0].first*P[0].first,0);
for(int i=0;i<N;i++) {
long long temp;
ret=query(P[i].second);
ret.first+=1LL*P[i].second*P[i].second+l;
temp=max(P[i].second-P[i+1].first,0);
update(-2LL*P[i+1].first,1LL*P[i+1].first*P[i+1].first+ret.first-temp*temp,++ret.second);
}
return ret;
}
long long take_photos(int N, int M, int K, vector<int> R, vector<int> C)
{
int i, j=0;
long long s=0, e=1e13;
P.resize(N);
for(i=0;i<N;i++) {
if(R[i]>C[i]) swap(R[i],C[i]);
P[i]={R[i],-C[i]};
}
sort(P.begin(),P.end());
for(i=0;i<N;i++) {
P[i].second=-P[i].second+1;
if(j==0 || P[j-1].first<P[i].first && P[j-1].second<P[i].second) {
P[j++]=P[i];
}
}
P.resize(j);
P.emplace_back(0x7fffffff,0x7fffffff);
K=min(K,j);
while(s<=e) {
long long m=(s+e)>>1;
if(solve(m).second>K) s=m+1;
else e=m-1;
}
auto t1=solve(e), t2=solve(s);
e=t1.first-e*t1.second;
s=t2.first-s*t2.second;
return e+(s-e)/max(t1.second-t2.second,1)*(t1.second-K);
}
