#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, M = 1e6+100;
const int inf = 2e18;
ll d[N][K];
ll t[N];
/*
struct line {
int k, b;
line () {
k = 0, b = inf;
}
line(int k, int b) : k(k), b(b) {}
int get(int x) {
return k * x + b;
}
};
struct LiChao {
line t[4 * M];
void add(int v, int tl, int tr, line q) {
int m = (tl + tr) / 2;
bool bl = q.get(tl) < t[v].get(tl), br = q.get(tr) < t[v].get(tr), bm = q.get(m) < t[v].get(m);
if (!bl && !br)
return;
if (bl && br) {
t[v] = q;
return;
}
if (bl != bm) {
line p = t[v];
t[v] = q;
add(2 * v + 1, tl, m, p);
} else {
line p = t[v];
t[v] = q;
add(2 * v + 2, m, tr, p);
}
}
int get(int v, int tl, int tr, int x) {
if (tl + 1 == tr)
return t[v].get(x);
int d, m = (tl + tr) / 2;
if (x < m)
d = get(2 * v + 1, tl, m, x);
else
d = get(2 * v + 2, m, tr, x);
return min(d, t[v].get(x));
}
};
*/
long long f(vector<int>&x , vector<int>& y, int lambda, int& k) {
int n = x.size();
vector<int> d(n, inf), s(n, 0);
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];
int prev = 0, seg = 0;
if (j) prev = d[j - 1], seg = s[j - 1];
int x = prev + c + lambda;
if (d[i] > x)
d[i] = x, s[i] = seg+1;
}
}
k = s.back();
return d.back();
}
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());
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();
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;
k = min(k, n);
int lo = -1, hi = 1e11;
while (hi - lo > 1) {
int c = (hi + lo) / 2;
int seg = 0;
f(x, y, c, seg);
if (seg > k)
lo = c;
else
hi = c;
}
int t;
int ans = f(x, y, hi, t);
ans -= hi * t;
return ans;
}
