#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
const int MAX_M = 505;
const long long INF = 1e18 + 7;
int N, M, K;
int a[MAX_M][MAX_M];
long long dp[MAX_M][MAX_M][MAX_M];
long long take_photos(int n, int m, int k, vector <int> r, vector <int> c) {
N = n, M = m, K = k;
for (int i = 0; i < N; i++) a[r[i] + 1][c[i] + 1]++;
for (int i = 1; i <= M; i++) {
for (int j = 1; j <= M; j++) a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
}
for (int i = 0; i <= K; i++) {
for (int j = 0; j <= M; j++) {
for (int n = 0; n <= N; n++) dp[i][n][j] = INF;
}
}
for (int i = 0; i <= M; i++) dp[0][0][i] = 0;
for (int i = 1; i <= K; i++) {
for (int j = 1; j <= M; j++) {
for (int n = 1; n <= N; n++) {
dp[i][n][j] = INF;
for (int k = j; k >= 1; k--) {
int cost = a[j][j] - a[k - 1][j] - a[j][k - 1] + a[k - 1][k - 1];
if (cost == 0 or n < cost) continue;
dp[i][n][j] = min(dp[i][n][j], dp[i - 1][n - cost][k - 1] + 1ll * (j - k + 1) * (j - k + 1));
}
// cout << i << ' ' << n << ' ' << j << " : " << dp[i][n][j] << endl;
}
}
}
long long ans = INF;
for (int i = 1; i <= K; i++) {
for (int j = 1; j <= M; j++) ans = min(ans, dp[i][N][j]);
}
return ans;
}
