#include "aliens.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define y1 asdfasdf123
#define ll long long
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#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();
pii arr[MAXN];
for (int i = 1; i <= n; i++) {
pii para = *it;
r[i] = para.first;
c[i] = para.second;
it++;
arr[i] = para;
}
sort(arr + 1, arr + n + 1, [&](pii a, pii b) {
if (a.sc != b.sc) {
return a.sc < b.sc;
} else {
return a.fr > b.fr;
}
});
vector <bool> used(n + 1, true);
vector <int> suf_r(n + 1);
suf_r[n] = arr[n].fr;
for (int i = n - 1; i >= 1; i--) {
suf_r[i] = min(arr[i].fr, suf_r[i + 1]);
}
vector <pii> nw;
for (int i = 1; i < n; i++) {
if (suf_r[i + 1] <= arr[i].fr) {
used[i] = false;
} else {
nw.push_back(arr[i]);
}
}
nw.push_back(arr[n]);
n = szof(nw);
for (int i = 0; i < n; i++) {
arr[i + 1] = nw[i];
r[i + 1] = nw[i].fr;
c[i + 1] = nw[i].sc;
}
// 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];
}
