#include "aliens.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
template<class T>
bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T>
bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
const int inf = 1001001001;
const ll linf = 1001001001001001001;
// Convex Hull Trix (Minimum)
class li_chao_tree {
int n;
vl xs;
// y = ax + b
vl a, b;
vi ls, rs;
ll eval(ll na, ll nb, int x) {
return na * xs[x] + nb;
}
void add(int k, ll na, ll nb) {
int l = ls[k], r = rs[k], m = (l + r) / 2;
if (l + 1 == r) {
if (eval(a[k], b[k], l) > eval(na, nb, l)) {
a[k] = na;
b[k] = nb;
}
return;
}
if (eval(a[k], b[k], l) <= eval(na, nb, l) and eval(a[k], b[k], r) <= eval(na, nb, r)) return;
if (eval(a[k], b[k], l) >= eval(na, nb, l) and eval(a[k], b[k], r) >= eval(na, nb, r)) {
a[k] = na;
b[k] = nb;
return;
}
if (eval(a[k], b[k], m) > eval(na, nb, m)) {
swap(a[k], na);
swap(b[k], nb);
}
if (eval(a[k], b[k], l) > eval(na, nb, l)) {
add(2 * k, na, nb);
return;
}
if (eval(a[k], b[k], r) > eval(na, nb, r)) {
add(2 * k + 1, na, nb);
return;
}
}
void init(const vl &_xs) {
n = 1;
while (n < (int) _xs.size()) n *= 2;
a.assign(2 * n, 0);
b.assign(2 * n, linf);
ls.resize(2 * n);
rs.resize(2 * n);
rep(i, n) {
ls[n + i] = i;
rs[n + i] = i + 1;
}
rrep(i, n) {
ls[i] = ls[2 * i];
rs[i] = rs[2 * i + 1];
}
xs.resize(n + 1, _xs.back() + 1);
rep(i, _xs.size()) xs[i] = _xs[i];
}
public:
li_chao_tree(const vl &_xs) {
assert(is_sorted(all(xs)));
init(_xs);
}
li_chao_tree(int n) {
vl v(n);
iota(all(v), 0);
init(v);
}
ll get_min(int i) {
assert(0 <= i and i < n);
int x = i;
i += n;
ll res = linf;
while (i >= 1) {
chmin(res, eval(a[i], b[i], x));
i >>= 1;
}
return res;
}
void add_line(ll na, ll nb) {
add(1, na, nb);
}
void add_segment(int l, int r, ll na, ll nb) {
assert(0 <= l and l <= r and r <= n);
l += n, r += n;
while (l < r) {
if (l & 1) add(l++, na, nb);
if (r & 1) add(--r, na, nb);
l >>= 1, r >>= 1;
}
}
};
ll take_photos(int n, int m, int k, vi r, vi c) {
vp v;
rep(i, n) {
if (r[i] <= c[i]) v.eb(r[i], c[i] + 1);
else v.eb(c[i], r[i] + 1);
}
sort(all(v));
vi ls;
int mx = 0;
rep(i, n) if (chmax(mx, v[i].second)) ls.pb(i);
int sz = ls.size();
vl s(sz), t(sz);
rep(i, sz) {
s[i] = v[ls[i]].first;
t[i] = v[ls[i]].second;
}
vector<li_chao_tree> dp(k + 1, li_chao_tree(t));
rep(i, sz) {
dp[1].add_line(-2 * s[0], s[0] * s[0]);
}
rep2(i, 1, sz) rep2(j, 1, k) {
ll now = dp[j].get_min(i - 1);
if (now == linf) continue;
now += t[i - 1] * t[i - 1];
rep2(ni, i, sz) {
ll lap = max(0LL, t[i - 1] - s[i]);
dp[j + 1].add_line(-2 * s[i], now - lap * lap + s[i] * s[i]);
}
}
ll ans = linf;
rep2(i, 1, k + 1) chmin(ans, dp[i].get_min(sz - 1) + t.back() * t.back());
return ans;
}
