#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,ik,pn;
long long dp[100009],ct[100009];
struct line{
int l,r;
bool operator<(const line &b)const{
return l < b.l || (l == b.l && r > b.r);
}
}ln[100009],ls[100009];
long long b(int x){
return dp[x] + 1ll * ln[x + 1].l * ln[x + 1].l - 1ll * max(0,ln[x].r - ln[x + 1].l) * max(0,ln[x].r - ln[x + 1].l);
}
long long k(int x){
return -2ll * ln[x + 1].l;
}
long long w(int x,long long fk){
return 1ll * ln[x].r * ln[x].r - fk;
}
bool chk1(int x,int y,int z){
//printf(" %d %d %d\n",x,y,z);
return (b(x) - b(z)) * (k(z) - k(y)) < (b(y) - b(z)) * (k(z) - k(x)) || ((b(x) - b(z)) * (k(z) - k(y)) == (b(y) - b(z)) * (k(z) - k(x)) && ct[x] <= ct[y]);
}
bool chk2(int x,int y,int t){
//printf(" %d %d\n",b(x) + k(x) * t,b(y) + k(y) * t);
return b(x) + k(x) * t > b(y) + k(y) * t || (b(x) + k(x) * t == b(y) + k(y) * t && ct[x] >= ct[y]);
}
int q[100009],head,tail;
void gt(long long fk){
dp[0] = 0;
ct[0] = 0;
head = tail = 1;
q[1] = 0;
for(int i = 1; i <= n; i ++){
//printf("%d %d\n",ln[i].l,ln[i].r);
while(head <= tail - 1 && chk2(q[head],q[head + 1],ln[i].r))
head ++;
dp[i] = b(q[head]) + k(q[head]) * ln[i].r + w(i,fk);
ct[i] = ct[q[head]] + 1;
//printf("%lld %d %lld %lld %lld\n",dp[i],q[head],k(q[head]),b(q[head]),w(i,fk));
if(k(q[tail]) == k(i) && b(q[tail]) == b(i) && ct[q[tail]] <= ct[i])
continue;
while(head <= tail - 1 && chk1(q[tail - 1],q[tail],i))
tail --;
q[++tail] = i;
}
//printf("%lld %lld %lld\n",fk,dp[n],ct[n]);
}
long long take_photos(int pn,int m,int ik,vector<int,std::allocator<int> >&r,vector<int,std::allocator<int> >&c){
for(int i = 1; i <= pn; i ++){
ls[i].l = r[i - 1],ls[i].r = c[i - 1];
if(ls[i].l > ls[i].r)
swap(ls[i].l,ls[i].r);
// printf(" %d %d\n",ls[i].l,ls[i].r);
}
sort(ls + 1,ls + pn + 1);
for(int i = 1; i <= pn; i ++){
if(i == 1 || ls[i].r >= ln[n].r)
ln[++n] = ls[i],ln[n].r ++;
//printf("%d\n",n);
}
long long l = -1ll * m * m - 9,rt = 1;
while(l + 1 < rt){
long long mid = (l + rt + 1) >> 1;
gt(mid);
if(ct[n] > ik)
rt = mid;
else
l = mid;
}
gt(l);
//printf("%d %d\n",ik,l);
return dp[n] + 1ll * ik * l;
}