#include "aliens.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define mk make_pair
#define sc second
#define fr first
#define pb push_back
using namespace std;
const long long N = (1e6 + 5);
const long long inf = (1e9 + 7);
pair<long long,long long> dp[1005][1005];
long long a[1005][1005];
long long cn = 0;
long long u[N];
long long mn;
long long ans = inf;
vector <long long> v;
long long f (long long mn,long long i,long long j,long long k) {
if (mn > v[j]) return 0;
return ((v[j] - max(mn,dp[j][k - 1].sc) + 1) * (v[j] - max(mn,dp[j][k - 1].sc) + 1));
}
long long take_photos(int n, int m, int kk, vector<int> r, vector<int> c) {
for (long long i = 0; i < m; i ++) u[i] = -1;
for (long long i = 0; i < n; i ++) {
if (u[max(r[i],c[i])] == -1) v.pb(max(r[i],c[i])),u[max(r[i],c[i])] = min(r[i],c[i]);
else u[max(r[i],c[i])] = min(u[max(r[i],c[i])],(long long)min(r[i],c[i]));
}
sort (v.begin(),v.end());
for (long long i = 0; i < v.size(); i ++)
for (long long k = 1; k <= kk; k ++)
dp[i][k].fr = inf;
mn = u[v[0]];
for (long long i = 0; i < v.size(); i ++) {
mn = min(mn,u[v[i]]);
dp[i][1].fr = (v[i] - mn + 1) * (v[i] - mn + 1);
dp[i][1].sc = u[v[i]];
}
for (long long k = 2; k <= kk; k ++) {
for (long long i = 0; i < v.size(); i ++) {
mn = u[v[i]];
for (long long j = i - 1; j >= 0; j --) {
if (dp[j][k - 1].fr + (v[i] - mn + 1) * (v[i] - mn + 1) - f(mn,i,j,k) < dp[i][k].fr)
dp[i][k].fr = dp[j][k - 1].fr + (v[i] - mn + 1) * (v[i] - mn + 1) - f(mn,i,j,k),dp[i][k].sc = mn;
mn = min(mn,u[v[j]]);
}
}
}
for (long long i = 1; i <= kk; i ++)
ans = min(ans,dp[(long long)v.size() - 1][i].fr);
return ans;
}
