#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
P arr[100000];
P temp[100000];
long long dp[4005][4005]; //dp[i][j] : minimum grid to fill if we should take a picture unitl i-th place with j pictures.
long long ans(int ind,int take) {
if (ind==-1) {
return 0;
}
if (take==0) {
return 1e18;
}
if (dp[ind][take]!=-1) {
return dp[ind][take];
}
long long ret=1e18;
for(int i=0;i<=ind;i++) {
long long val=ans(i-1,take-1)*4;
val+=((long long)arr[ind].second-arr[i].first+2)*(arr[ind].second-arr[i].first+2);
if (i>0&&arr[i-1].second-arr[i].first+2>0) {
val-=((long long)arr[i-1].second-arr[i].first+2)*(arr[i-1].second-arr[i].first+2);
}
val/=4;
ret=min(ret,val);
}
dp[ind][take]=ret;
return ret;
}
bool comp(P a,P b) {
if (a.second==b.second) {
return a.first<b.first;
}
return a.second<b.second;
}
long long take_photos(int n,int m,int k,vector<int> r,vector<int> c) {
memset(dp,-1,sizeof(dp));
for(int i=0;i<n;i++) {
if (r[i]>c[i]) {
swap(r[i],c[i]);
}
temp[i]=P(2*r[i]+1,2*c[i]+1);
}
sort(temp,temp+n,comp);
int sz=0;
int mini=1e8;
for(int i=n-1;i>=0;i--) {
if (temp[i].first<mini) {
arr[sz++]=temp[i];
}
mini=min(mini,temp[i].first);
}
n=sz;
reverse(arr,arr+n);
return ans(n-1,k);
}
