#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define for2(a,b,c) for(int a=b;a < c; a++)
#include "aliens.h"
int dp[510][1010];
int tmp[510][1010];
int R[1010];
int C[1010];
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
if (n > 500) return -1;
fill(R,R+m+2,(1e9));
fill(C,C+m+2,(1e9));
for2(i,0,n){
R[r[i]]= min(R[r[i]],c[i]);
C[c[i]]= min(C[c[i]],r[i]);
}
for2(i,0,510) for2(j,0,1010){
if(i <= k) dp[i][j] = 0;
else dp[i][j] = 1e9;
}
for2(i,1,m+1){
for2(i,0,510) for2(j,0,1010){
tmp[i][j] = dp[i][j];
dp[i][j] = (1e9);
}
for2(j,0,k+1) for2(t,0,i+1){
int nt = t;
nt = min(nt,C[i-1]);
nt = min(nt,R[i-1]);
if(j) dp[j][t] = min((ll)dp[j][t],tmp[j-1][nt] + (i-nt)*1ll*(i-nt) - (i-t)*1ll*(i-t) );
if(nt == t) dp[j][t] = min(dp[j][t],tmp[j][t]);
if(nt == t && nt == i){
dp[j][t] = min(dp[j][t],tmp[j][t-1]);
}
}
}
return dp[k][m];
}
