#include "aliens.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAX_N = 101;
const ll infinity = 1e18;
ll dp[MAX_N][MAX_N];
int ind[MAX_N];
//bool grid[MAX_N][MAX_N];
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
// for (int i = 0; i < n; i++) {
// if (r[i] > c[i]) swap(r[i], c[i]);
// for (int x = r[i]; x <= c[i]; x++) {
// for (int y = r[i]; y <= c[i]; y++) {
// grid[x][y] = true;
// }
// }
// }
// ll ans = 0;
// for (int i = 0; i < m; i++) {
// for (int j = 0; j < m; j++) {
// ans += grid[i][j];
// }
// }
// return ans;
iota(ind, ind + n, 0);
sort(ind, ind + n, [&] (int i, int j) {
return r[i] + c[i] < r[j] + c[j];
});
fill(dp[0], dp[0] + n, infinity);
for (int j = 1; j <= k; j++) {
for (int i = 0; i < n; i++) {
dp[j][i] = infinity;
int left = m, right = 0;
for (int l = i; l >= 0; l--) {
chkmin(left, r[ind[l]]);
chkmax(right, c[ind[l]] + 1);
ll x = (l ? dp[j - 1][l - 1] : 0) + ll(right - left) * (right - left);
chkmin(dp[j][i], x);
}
}
}
return dp[k][n - 1];
}
