#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
using ll = long long;
using pli = pair<ll, int>;
using pii = pair<int, int>;
#define F first
#define S second
struct CHT {
struct line {
ll m, c;
int cnt;
line(ll m, ll c, int cnt) : m(m), c(c), cnt(cnt) {}
ll get(ll x) { return m*x + c; }
};
bool bad(line l1, line l2, line l3) {
return (l3.c-l1.c)*(l1.m-l2.m) <= (l2.c-l1.c)*(l1.m-l3.m);
}
vector<line> f;
int idx;
void update(ll m, ll c, int cnt) {
line l(m, c, cnt);
while (f.size() > 1 && bad(f[f.size()-2], f[f.size()-1], l))
f.pop_back();
f.push_back(l);
}
pli query(ll x) {
while (idx < f.size()-1 && f[idx].get(x) > f[idx+1].get(x))
++idx;
return pli(f[idx].get(x), f[idx].cnt);
}
void clear() {
f.clear();
idx = 0;
}
} cht;
int n;
vector<pii> A;
void compress()
{
sort(A.begin(), A.end(), [&] (pii a, pii b) {
return pii(a.F, -a.S) < pii(b.F, -b.S);
});
vector<pii> ret;
int en = -1;
for (auto x : A) if (x.S > en)
ret.push_back(x), en = x.S;
A = ret;
n = A.size();
A.insert(A.begin(), pii(-1e7, -1e7));
}
inline ll sq(ll x) { return x*x; }
pli solve(ll C)
{
vector<pli> dp(n+1);
cht.clear();
dp[0] = pli(0, 0);
for (int i = 1; i <= n; ++i) {
cht.update(-2*A[i].F+2, sq(A[i].F-1)+dp[i-1].F-sq(max(0, A[i-1].S-A[i].F+1)), dp[i-1].S);
pli q = cht.query(A[i].S);
dp[i] = pli(q.F + sq(A[i].S) + C, q.S+1);
}
return dp[n];
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
for (int i = 0; i < n; ++i)
A.push_back(minmax(r[i], c[i]));
compress();
ll b = 0, e = 1e17;
while (b < e) {
ll v = (b+e)/2;
if (solve(v).S <= k) e = v;
else b = v+1;
}
return solve(b).F - b*k;
}
