#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;
}