#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define ll long long
//typedef long long int;
typedef pair<int, int> pii;
typedef vector<int> vi;
#ifdef LOCAL_DEFINE
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#endif
#include "aliens.h"
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
/*
dp[i][k] = dp[j][k - 1] + area(j + 1, i)
make new vector and add the points which matter in it
*/
vector<pair<int, int>> temp;
for(int i = 0; i < n; i++){
if(r[i] > c[i]){
int a = c[i];
c[i] = r[i];
r[i] = a;
}
temp.emplace_back(c[i], r[i]);
}
sort(temp.begin(), temp.end(), [](pair<int, int> x, pair<int, int> y){
if(x.first == y.first) return x.second < y.second;
return x.first < y.first;
});
vector<int> useless(n+1, 0);
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
if(useless[i] or useless[j]) continue;
if(temp[i].second >= temp[j].second){
useless[j] = 1;
}
}
}
vector<pair<int, int>> final;
for(int i = 0, j = 0; i < n; i++){
if(!useless[i]){
final.emplace_back(temp[i].first, temp[i].second);
//cout << final[j].first << ' ' << final[j].second << '\n';
j++;
}
}
auto area = [&](int x, int y){
if(x == 0){
return (final[y].first - final[x].second + 1)*(final[y].first - final[x].second + 1);
}
else{
return (final[y].first - final[x].second + 1)*(final[y].first - final[x].second + 1) - max(0, (final[x-1].first - final[x].second + 1)*(final[x-1].first - final[x].second + 1));
}
};
n = final.size();
int dp[n+2][n+2];
memset(dp, 0x3f, sizeof dp);
//dp[0][1] = 1;
//dp[0][0] = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j <= i; j++){
for(int l = 1; l <= k; l++){
if(l == 1){
dp[i][l] = area(0, i);
}
else{
dp[i][l] = min(dp[i][l-1], dp[j][l-1] + area(j+1, i));
}
}
}
}
return dp[n-1][k];
}
