#include "aliens.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define y1 asdfasdf123
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 505;
const int MAXM = 1005;
bool used[155][155];
ll dp[MAXN][MAXN];
int r[MAXN];
int c[MAXN];
int n, m, k;
ll cost(int l, int r) {
return (r - l + 1ll) * (r - l + 1ll);
}
void f(int y1, int x1, int y2, int x2) {
for (int i = y1; i <= y2; i++) {
for (int j = x1; j <= x2; j++) {
used[i][j] = true;
}
}
}
int subtask1() {
for (int i = 1; i <= n; i++) {
int mn = min(r[i], c[i]);
int mx = max(r[i], c[i]);
f(mn, mn, mx, mx);
}
long long ans = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= m; j++) {
if (used[i][j]) {
ans++;
}
}
}
return ans;
}
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++) {
r[i + 1] = R[i] + 1;
c[i + 1] = C[i] + 1;
}
if (n <= 50 && m <= 100 && k == n) {
return subtask1();
}
memset(dp, INF, sizeof(dp));
dp[0][0] = 0;
for (int gr = 1; gr <= k; gr++) {
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
dp[gr][i] = min(dp[gr][i], dp[gr - 1][j] + cost(j + 1, i));
}
}
}
assert(dp[k][n] != INF);
return dp[k][n];
}
