#include<cstdio>
#include<algorithm>
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]);
}
int main(){
	scanf("%d %d %d",&pn,&m,&ik);
	for(int i = 1; i <= pn; i ++){
		scanf("%d %d",&ls[i].l,&ls[i].r);
		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,r = 1;
	while(l + 1 < r){
		long long mid = (l + r + 1) >> 1;
		gt(mid);
		if(ct[n] > ik)
			r = mid;
		else
			l = mid;
	}
	gt(l);
	//printf("%d %d\n",ik,l);
	printf("%lld\n",dp[n] + 1ll * ik * l);
}

answer.code: In function ‘int main()’:
answer.code:51:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   51 |         scanf("%d %d %d",&pn,&m,&ik);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
answer.code:53:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   53 |                 scanf("%d %d",&ls[i].l,&ls[i].r);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccpyzbAX.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/cc1Lh9CY.o:implementer.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc1Lh9CY.o: in function `main':
implementer.cpp:(.text.startup+0xff): undefined reference to `take_photos(int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status