#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;

long long dp[1000001],a,b,cn,g[1000001],f[1000001];
struct p{long long q,w;}l[1000001],m[1000001];
bool cmp(p qq,p ww){if(qq.q==ww.q) return qq.w>ww.w;return qq.q<ww.q;}
void ch(long long qq)
{
	dp[0]=0,g[0]=0;
	for(int i=1;i<=b;i++)
	{
		dp[i]=1e18,g[i]=0;
		for(int j=0;j<i;j++)
		{
			long long tt=dp[j]+(m[i].w+1-m[j+1].q)*(m[i].w+1-m[j+1].q)-f[j]+qq;
//			cout<<tt<<" "<<dp[j]<<" "<<f[j]<<"\n";
			if(tt<dp[i]) dp[i]=tt,g[i]=g[j]+1;
			else if(tt==dp[i]&&g[j]+1<g[i]) dp[i]=tt,g[i]=g[j]+1;
		}
	}
//	cout<<qq<<" "<<dp[b]<<" "<<g[b]<<"\n";
}
long long take_photos(int n, int mm, int k, std::vector<int> r, std::vector<int> c) {
	a=n,b=mm;
	swap(a,b);
	long long ll=0,rr=1e12;
	for(int i=0;i<b;i++)
	{
		if(r[i]<c[i]) l[i+1]=p{r[i]+1,c[i]+1};
		else l[i+1]=p{c[i]+1,r[i]+1};
	}
	sort(l+1,l+b+1,cmp);
	long long mxx=0;
	for(int i=1;i<=b;i++)
	{
//		cout<<l[i].q<<" "<<l[i].w<<"\n";
		if(cn>0&&m[cn].w>=l[i].w) continue;
		else m[++cn]=l[i];
	}b=cn;
	for(int i=1;i<b;i++)
	{
		if(m[i].w>=m[i+1].q) f[i]=(m[i].w-m[i+1].q+1)*(m[i].w-m[i+1].q+1);
		assert(f[i]==0);
		assert(m[i].q!=m[i-1].q);
	}
//	cout<<b<<"\n";
//	for(int i=1;i<=b;i++) cout<<m[i].q<<" "<<m[i].w<<"\n";
//	exit(0);
	long long ann=0;
	while(ll<=rr)
	{
		long long mid=((ll+rr)>>1);
		ch(mid);
		if(g[b]<=k) ann=mid,rr=mid-1;
		else ll=mid+1;
	}
	ch(ann);
    return dp[b]-g[b]*ann;
}

//int main() {
//    int n, m, k;
//    assert(3 == scanf("%d %d %d", &n, &m, &k));
//    std::vector<int> r(n), c(n);
//    for (int i = 0; i < n; i++) {
//        assert(2 == scanf("%d %d", &r[i], &c[i]));
//    }
//    long long ans = take_photos(n, m, k, r, c);
//    
//    
//    printf("%lld\n", ans);
//    return 0;
//}