#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
const int nax = 503;
const long long INF = 1e18;
int N, K;
vector<int>col_tag, row_tag;
long long dp[nax][nax];
long long sq(long long x) {
return x * x;
}
long long solve(int i, int j) {
if(j>K) return INF;
if(i==N) return 0LL;
long long &ret = dp[i][j];
if(ret!=-1) return ret;
ret = INF;
int deepest = 0;
for(int k=i+1; k<=N; ++k) {
deepest = max(deepest, row_tag[k-1]);
long long dimen = deepest - col_tag[i] + 1;
long long isec = 0;
if(k<N && col_tag[k]<=deepest) {
isec = sq((deepest - col_tag[k] + 1));
}
if(k==N) {
ret = min(ret, sq(dimen) + solve(k, j+1));
break;
}
if(row_tag[k]<deepest) continue;
ret = min(ret, solve(k, j+1) + sq(dimen) - isec);
}
return ret;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
map<int,int>deep;
for(int i=0; i<n; ++i) {
if(r[i] < c[i]) swap(r[i], c[i]);
deep[c[i]] = max(deep[c[i]], r[i]);
}
for(auto it : deep) {
col_tag.push_back(it.first);
row_tag.push_back(it.second);
}
n = col_tag.size();
N = n;
K = k;
memset(dp, -1, sizeof dp);
return solve(0, 0);
}
