#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int mxN = 1e5;
vector<int> stk;
ll n, m, k, dp[mxN], pho[mxN], bst, l[mxN], r[mxN];
ll sqr(ll x) {return x*x;}
struct line {ll m, c, pcnt;};
vector<line> lines;
long double sect(line a, line b) {return (long double)(a.m - b.m) / (b.c - a.c);}
const long double EPS = 1e-15;
ll eval(line l, ll x) {return l.m*x + l.c;}
void upd(line l) {
while (lines.size() > 1 && sect(l, lines[lines.size()-2]) < sect(l, lines.back())) {
lines.pop_back();
}
while (lines.size() > 1 && fabs(sect(l, lines[lines.size()-2]) - sect(l, lines.back())) < EPS && l.pcnt <= lines.back().pcnt) {
lines.pop_back();
}
lines.push_back(l);
bst = min(bst, (ll)lines.size()-1);
}
line qry(ll x) {
while (bst < lines.size()-1 && ((eval(lines[bst+1], x) < eval(lines[bst], x)) || (eval(lines[bst+1], x) == eval(lines[bst], x) && lines[bst+1].pcnt <= lines[bst].pcnt))) bst++;
return lines[bst];
}
int slv(ll cst) {
lines.clear();
upd({-2*l[stk[0]], sqr(l[stk[0]]), 0});
for (int i = 0; i < stk.size(); ++i) {
ll ri = r[stk[i]]+1;
line res = qry(ri);
dp[i] = cst + sqr(ri) + eval(res, ri);
pho[i] = res.pcnt + 1;
if (i+1 < stk.size()) upd({-2*l[stk[i+1]], dp[i] - sqr(max(0ll,ri-l[stk[i+1]])) + sqr(l[stk[i+1]]), pho[i]});
}
return pho[stk.size() - 1];
}
ll take_photos(int N, int m, int k, vector<int> R, vector<int> C) {
n = N;
for (int i = 0; i < n; ++i) {
l[i] = min(R[i], C[i]);
r[i] = max(R[i], C[i]);
}
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b){return r[a] < r[b];});
for (int i: order) {
while (stk.size() && l[stk.back()] >= l[i]) stk.pop_back();
stk.push_back(i);
}
ll lo = 0, hi = (ll)m*m, mid;
while (lo != hi) {
mid = lo+hi>>1;
if (slv(mid) <= k) hi = mid;
else lo = mid + 1;
}
slv(lo);
return dp[stk.size()-1] - k*lo;
}
