#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
const ll INF = 1e18;
int n, m, k;
vl r, c, L, R;
void preprocess(int N, int M, int K, vi Row, vi Col) {
vector<int> sorted_points(N); iota(sorted_points.begin(), sorted_points.end(), 0);
sort(sorted_points.begin(), sorted_points.end(), [&](int a, int b) {
ll La = min(Row[a], Col[a]), Ra = max(Row[a], Col[a]), Lb = min(Row[b], Col[b]), Rb = max(Row[b], Col[b]);
return La == Lb ? Ra > Rb : La < Lb;
});
vector<int> points; int lastR = -1;
for (int i = 0; i < N; i++) {
int cur = sorted_points[i];
int rcur = max(Row[cur], Col[cur]);
if (rcur > lastR) {
points.push_back(cur);
lastR = rcur;
}
}
n = points.size(); m = M; k = K;
r.resize(n); c.resize(n); L.resize(n); R.resize(n);
for (int i = 0; i < n; i++) {
r[i] = Row[points[i]]; c[i] = Col[points[i]];
L[i] = min(r[i], c[i]);
R[i] = max(r[i], c[i]);
}
}
struct Function {
ll b, c;
ll seg;
Function(ll B = 0, ll C = INF, ll s = 0) : b(B), c(C), seg(s) {};
ll evaluate(ll x) {
return x*x + b*x + c;
}
};
bool better(Function& f1, Function& f2, ll x) {
ll v1 = f1.evaluate(x), v2 = f2.evaluate(x);
if (v1 != v2) return v1 < v2;
return f1.seg < f2.seg;
}
struct Node {
Function best;
Node *left, *right;
Node() : best(Function()), left(nullptr), right(nullptr) {};
Node(Function Best) : best(Best), left(nullptr), right(nullptr) {};
};
// implicit segtree storing minimum function at x for x in [0, 1m]
struct LiChaoTree {
int lower, upper;
Node* root;
LiChaoTree() {};
LiChaoTree(int L, int U) {
lower = L;
upper = U;
root = new Node();
}
Node* update(Node* cur, int l, int r, Function fnew) {
if (!cur) cur = new Node();
int m = l + (r - l) / 2;
if (better(fnew, cur->best, m)) swap(cur->best, fnew);
if (better(fnew, cur->best, l)) cur->left = update(cur->left, l, m, fnew);
else if (better(fnew, cur->best, r)) cur->right = update(cur->right, m, r, fnew);
return cur;
}
pair<ll, ll> query(Node* cur, int l, int r, ll x) {
if (!cur) return {INF, 0};
pair<ll, ll> our_val = {cur->best.evaluate(x), cur->best.seg};
if (l + 1 == r) return our_val;
int m = l + (r - l) / 2;
if (x < m) return min(our_val, query(cur->left, l, m, x));
else return min(our_val, query(cur->right, m, r, x));
}
void update(Function fnew) {
update(root, lower, upper+1, fnew);
}
pair<ll, ll> query(ll x) {
return query(root, lower, upper+1, x);
}
};
void compute_dp(ll lambda, vl& dp, vl &cnt, const vl &overlap) {
dp.assign(n, INF);
cnt.assign(n, 0);
LiChaoTree lct(0, m+1);
ll L0 = L[0] - 1;
lct.update(Function(-2*L0, L0*L0 + lambda, 1));
auto r0 = lct.query(R[0]);
dp[0] = r0.first;
cnt[0] = r0.second;
for (int i = 1; i < n; ++i) {
ll Lj = L[i] - 1;
ll B = -2 * Lj;
ll C = dp[i-1] + Lj*Lj + lambda - overlap[i];
int nseg = cnt[i-1] + 1;
lct.update(Function(B, C, nseg));
auto res = lct.query(R[i]);
dp[i] = res.first;
cnt[i] = res.second;
}
}
ll take_photos(int N, int M, int K, vi Row, vi Col) {
preprocess(N, M, K, Row, Col);
vl overlap(n, 0);
for (int i = 1; i < n; i++) {
ll over = max(0LL, R[i-1] - L[i] + 1);
over *= over;
overlap[i] = over;
}
ll lo = 0, hi = 1e13;
vector<ll> dp, cnt;
while (lo < hi) {
ll mid = (lo + hi) >> 1;
compute_dp(mid, dp, cnt, overlap);
if (cnt.back() > k) lo = mid + 1;
else hi = mid;
}
compute_dp(lo, dp, cnt, overlap);
return dp.back() - 1LL * lo * k;
}
