#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 inf = 2e18;
void calc(int l, int r, int opt_l, int opt_r, int j, vector<int>& x, vector<int>& y, vector<int>& t, vector<vector<int>>& d) {
if (l > r) return;
int opt = opt_l;
int i = (l + r) / 2;
for (int f = opt_l; f <= min(i - 1, opt_r); f++) {
ll c = d[f][j - 1] + sqr(x[i - 1] - y[f] + 1) - t[f];
if (c < d[i][j])
d[i][j] = c, opt = f;
}
calc(l, i - 1, opt_l, opt, j, x, y, t, d);
calc(i + 1, r, opt, opt_r, j, x, y, t, d);
}
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;
for (pii p : a) {
while (st.size() && st.back().second >= p.second)
st.pop_back();
st.push_back(p);
}
n = st.size();
k = min(k, n);
vector<int> x(n), y(n);
for (int i = 0; i < n; i++)
x[i] = st[i].first, y[i] = st[i].second;
vector<int> t(n, 0);
for (int i = 1; i < n; i++)
t[i] = sqr(max(0ll, x[i - 1] - y[i] + 1));
vector<vector<int>> d(n + 1, vector<int>(k + 1, inf));
for (int j = 0; j <= k; j++)
d[0][j] = 0;
for (int j = 1; j <= k; j++)
calc(1, n, 0, n, j, x, y, t, d);
return d.back().back();
}
