#include "aliens.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define y1 asdfasdf123
#define ll long long
#define szof(s) (int)s.size()
#define pii pair<int, int>
#define fr first
#define sc second
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;
int S(int x) {
return x * x;
}
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;
}
/*
1 2 1
0 1
*/
int cost(int left, int right) {
return S(c[right] - r[left] + 1) - (left - 1 > 0 ? S(max(0, c[left - 1] - r[left] + 1)) : 0);
}
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();
}
for (int i = 1; i <= n; i++) {
if (r[i] > c[i]) {
swap(r[i], c[i]);
}
}
// r[i] <= c[i];
set <pii> st;
for (int i = 1; i <= n; i++) {
st.insert({r[i], c[i]});
}
n = szof(st);
auto it = st.begin();
for (int i = 1; i <= n; i++) {
pii para = *it;
r[i] = para.first;
c[i] = para.second;
it++;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
continue;
}
if (r[i] <= r[j] && c[j] <= c[i]) {
st.erase({r[j], c[j]});
}
}
}
n = szof(st);
it = st.begin();
for (int i = 1; i <= n; i++) {
pii para = *it;
r[i] = para.first;
c[i] = para.second;
it++;
}
// a[i] не внутри a[j] i != j
k = min(k, n);
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 lst = 0; lst < i; lst++) {
dp[gr][i] = min(dp[gr][i], dp[gr - 1][lst] + cost(lst + 1, i));
}
}
}
return dp[k][n];
}
