#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
long long solve1(int n, int m, int k, vector<int> r, vector<int> c){
vector<vector<bool>> grid(m, vector<bool>(m));
for (int i = 0; i < n; ++i){
for (int j = min(r[i], c[i]); j <= max(r[i], c[i]); ++j){
for (int l = min(r[i], c[i]); l <= max(r[i], c[i]); ++l) grid[j][l] = true;
}
}
int ans = 0;
for (int i = 0; i < m; ++i){
for (int j = 0; j < m; ++j){
if (grid[i][j]) ans++;
}
}
return ans;
}
long long solve2(int n, int m, int k, vector<int> r, vector<int> c){
sort(r.begin(), r.end());
vector< vector<int> > dp(n+1, vector<int>(k+1, m * m));
dp[0][0] = 0;
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= min(i, k); ++j){
dp[i][j] = min(dp[i][j], dp[i][j-1]);
for (int l = 0; l < i; ++l){
dp[i][j] = min(dp[i][j], dp[l][j-1] + (r[i-1] - r[l] + 1) * (r[i-1] - r[l] + 1));
}
}
}
return dp[n][k];
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
if (n <= 50) return solve1(n, m, k, r, c);
else return solve2(n, m, k, r, c);
}
