#include<bits/stdc++.h>
#define MAXN 1007
using namespace std;
const long long inf=1e17;
long long dp[MAXN][MAXN];
struct interval{
int l,r;
inline friend bool operator < (interval fr,interval sc){
if(fr.l==sc.l)return fr.r>sc.r;
return fr.l<sc.l;
}
}s[MAXN],w[MAXN];
int n,m,k,sz;
long long area(long long l,long long r){
if(l>r)return 0;
return (r-l+1)*(r-l+1);
}
long long cost(int l,int r){
return area(w[l].l,w[r].r) - area(w[l].l,w[l-1].r);
}
long long take_photos(int N, int M, int K, vector<int> r, vector<int> c){
n=N; m=M; k=K;
for(int i=1;i<=n;i++){
s[i]={min(r[i-1],c[i-1])+1,max(r[i-1],c[i-1])+1};
}
sort(s+1,s+n+1);
for(int i=1;i<=n;i++){
if(sz>0 and s[i].r<=w[sz].r)continue;
sz++; w[sz]=s[i];
}
for(int i=1;i<=sz;i++){
dp[i][0]=inf;
for(int f=1;f<=k;f++){
dp[i][f]=inf;
for(int t=i;t>=1;t--){
dp[i][f]=min(dp[i][f],dp[t-1][f-1] + cost(t,i));
}
}
}
return dp[sz][k];
}
/*int main(){
cout<<take_photos(5, 7, 2, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6})<<"\n";
return 0;
}*/
