#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define sqr(x) ((x)*(x))
using pii = pair<int, int>;
const int N = 4001, K = 4001;
const int inf = 2e18;
ll d[N][K];
ll t[N];
long long take_photos(signed n, signed m, signed k, std::vector<signed> r, std::vector<signed> c) {
vector<pii> a(n);
for (int i = 0; i < n; i++) a[i] = {max(r[i], c[i]), min(r[i], c[i])};
sort(a.begin(), a.end()/*, [](pii a, pii b) {return a.first < b.first || a.first == b.first && a.second > b.second;}*/);
vector<pii> st;
int mx = -1;
for (pii p : a) {
//if (p.second == mx)
// st.pop_back();
if (p.second >= mx)
st.push_back(p), mx = p.second;
}
n = st.size();
vector<int> x(n), y(n);
for (int i = 0; i < n; i++)
x[i] = st[i].first, y[i] = st[i].second;
for (int i = 0; i < n; i++) {
if (i)
t[i] = max(0ll, x[i - 1] - y[i] + 1);
t[i] = sqr(t[i]);
t[i] = sqr(y[i]) - t[i];
}
for (int i = 0; i < n; i++)
for (int w = 0; w <= k; w++)
d[i][w] = inf;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
ll c = sqr(x[i] + 1) - 2 * (x[i] + 1) * y[j] + t[j];
for (int w = 1; w <= k; w++) {
int prev = 0;
if (j)
prev = d[j - 1][w - 1];
d[i][w] = min(d[i][w], prev + c);
}
}
}
return d[n - 1][k];
}
