#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 100010, MAX_K = 17;
const ll inf = 1ll << 55;
#include "aliens.h"
ll sq(ll v) { return v * v; }
vector<int> allc;
void monolize(vector<int> &r, vector<int> &c, int &n) {
for (int i = 0;i < n;++i) {
if (r[i] > c[i]) swap(r[i], c[i]);
}
vector<pair<int,int>> loc;
for (int i = 0;i < n;++i) loc.pb(c[i], r[i]);
sort(AI(loc));
int sz = 0;
for (auto [x, y] : loc) {
while (sz) {
auto [xx, yy] = loc[sz-1];
if (yy < y) break;
--sz;
}
loc[sz++] = {x, y};
}
loc.resize(sz);
r.clear(), c.clear();
for (auto [x, y] : loc)
r.pb(y), c.pb(x);
n = r.size();
}
ll sp[MAX_K][MAX_N];
ll qry(int l, int r) {
int lg = __lg(r-l);
return min(sp[lg][l], sp[lg][r - (1<<lg)]);
}
void init_rmq(int g, vector<int> r, vector<int> c) {
vector<int> allc(c); allc.pb(-1); sort(AI(allc)), allc.erase(unique(AI(allc)), end(allc));
auto get_pos = [&](int c) -> int {
return lower_bound(AI(allc), c) - begin(allc);
};
fill(sp[0], sp[0] + g, inf);
for (int i = 0;i < r.size();++i) {
int j = get_pos(c[i]);
chmin(sp[0][j], (ll)r[i]);
}
for (int d = 1;d < MAX_K;++d)
for (int i = 0;i < g;++i)
sp[d][i] = min(sp[d-1][i], sp[d-1][ min(g-1, i + (1<<(d-1))) ]);
}
ll cost(int l, int i) {
ll mnc = qry(l+1, i+1), wid = allc[i] - mnc + 1, rep = max<ll>(0, allc[l] - mnc + 1);
return sq(wid) - sq(rep);
}
ll dp[MAX_N], cnt[MAX_N];
int fr[MAX_N], ti[MAX_N];
pair<ll,ll> get_dp(ll C, int g) {
fill(dp+1, dp+g, inf);
int *hf = fr, *ef = fr, *ht = ti, *et = ti;
*ef++ = 0, *et++ = -1;
for (int i = 1;i < g;++i) {
if (et-ht > 1 && ht[1] <= i)
++hf, ++ht;
auto trans = [&](int l, int i) {
return cost(l, i) + dp[l];
};
dp[i] = C + trans(hf[0], i);
cnt[i] = cnt[ hf[0] ] + 1;
auto better = [&](int a, int b) {
int l = i+1, r = g, mid;
while (l < r) {
mid = l + r >> 1;
if (trans(a, mid) < trans(b, mid))
r = mid;
else
l = mid+1;
}
return l;
};
int nt = better(i, ef[-1]);
while (ef-hf > 1) {
if (nt > et[-1]) break;
--ef, --et;
nt = better(i, ef[-1]);
}
if (nt < g) *ef++ = i, *et++ = nt;
}
return make_pair(cnt[g-1], dp[g-1]);
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
monolize(r, c, n);
allc = c;
allc.pb(-1); sort(AI(allc)), allc.erase(unique(AI(allc)), end(allc));
int g = allc.size();
init_rmq(g, r, c);
ll L = 0, R = ((1ll << 40)-1 + k-1) / k, M;
while (L < R) {
M = L + R >> 1;
auto [u, w] = get_dp(M, g);
if (u > k)
L = M+1;
else R = M;
}
auto [u, w] = get_dp(L, g);
return w - L * k;
}
