#include "aliens.h"
#include <algorithm>
using namespace std;
struct A
{
long long a;
long long b;
}Node[100005];
long long DP[4005][4005]={0};
bool have[4005][4005];
long long tt[4005];
bool cmp(A a,A b)
{
return a.a<b.a||a.a==b.a&&a.b<b.b;
}
long long F(int N,int M)
{
long long i;
if(N==-1) return 0;
if(M==0) return 1e18;
if(have[N][M]) return DP[N][M];
DP[N][M]=1e18;
//printf("%lld %lld\n",N,max((long long) 0,Node[N].a-tt[N+1]));
for(i=N;i>=0;i--) DP[N][M]=min(DP[N][M],F(i-1,M-1)+(Node[N].a-min(Node[N].b,Node[i].b)+1)*(Node[N].a-min(Node[N].b,Node[i].b)+1)-max((long long) 0,Node[N].a-tt[N+1])*max((long long) 0,Node[N].a-tt[N+1]));
//printf("%d %d %lld\n",N,M,DP[N][M]);
return DP[N][M];
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c)
{
int i;
for(i=0;i<n;i++)
{
Node[i].a=(long long) max(r[i],c[i]);
Node[i].b=(long long) min(r[i],c[i]);
}
sort(Node,Node+n,cmp);
tt[n]=1e9;
for(i=n-1;i>=0;i--)
{
tt[i]=min(tt[i+1],Node[i].b);
}
//for(i=0;i<n;i++) printf("%d %d\n",Node[i].a,Node[i].b);
return F(n-1,k);
}
