#include "aliens.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define f first
#define se second
//#define int long long
#define pll pair<ll, ll>
#define pii pair<int, int>
using namespace std;
const int N = 3e5 + 123;
//const int N = 2e4 + 123;
const int M = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll inf = 1e16;
const ld INF = 1e17;
const ll maxR = 1e14;
struct segment {
ll l, r, l1, r1;
segment(ll l, ll r, ll l1, ll r1) : l(l), r(r), l1(l1), r1(r1) {};
};
struct line {
ll b, k;
ll cntid;
};
vector <line> lines;
ld intersect(line l1, line l2) {
return (l1.b * 1.0 - l2.b * 1.0) / (l2.k * 1.0 - l1.k * 1.0);
}
ld val(line l, ld x) {
return l.k * 1.0 * x + l.b;
}
ll vall(line l, ll x) {
return l.k * x + l.b;
}
void addline(line a) {
while (lines.size() > 1) {
ld tmp = intersect(lines[lines.size() - 1], lines[lines.size() - 2]);
if (val(lines[lines.size() - 1], tmp) > val(a, tmp))
lines.pop_back();
else
break;
}
lines.pb(a);
}
pair<ll, ll> getmin(ll x) {
ll L, R, M;
pair<ll, ll> ans = {inf, inf};
L = 0; R = lines.size() - 1;
while (L <= R) {
M = (L + R) / 2;
ans = min(ans, {vall(lines[M], x), lines[M].cntid});
if (M == lines.size() - 1) {
R = M - 1;
continue;
}
if (make_pair(vall(lines[M], x), lines[M].cntid) >= make_pair(vall(lines[M + 1], x), lines[M + 1].cntid))
L = M + 1;
else
R = M - 1;
}
return ans;
}
ll L[N], R[N], Lto[N], Rto[N], ar[N], sz = 0;
ll cntt[N];
bool isworth[N];
vector <segment> worth;
vector <ll> byl[N];
unordered_set <ll> st[M];
ll dp[N];
bool cmp(segment x, segment y) {
return x.r < y.r;
}
ll cost(ll l, ll r) {
if (l > r)
return 0;
return (r - l + 1) * (r - l + 1);
}
void add(int j) {
line tmp;
tmp.b = dp[j - 1] + worth[j].l * worth[j].l- cost(worth[j].l, worth[j - 1].r);
tmp.k = -2 * worth[j].l;
tmp.cntid = cntt[j - 1];
addline(tmp);
}
void count(ll costt, int n) {
lines.clear();
dp[1] = cost(worth[1].l, worth[1].r) + costt;
cntt[1] = 1;
for (int i = 2; i <= n; i++) {
add(i);
pair<ld, ll> tmpp = getmin(worth[i].r + 1);
dp[i] = costt + tmpp.f + (worth[i].r + 1) * (worth[i].r + 1);
cntt[i] = tmpp.se + 1;
}
}
ll take_photos(int n, int m, int k, vector <int> r, vector <int> c) {
int tmp = 0;
for (int i = 0; i < n; i++) {
if (c[i] >= r[i]) {
if (st[r[i] + 1].count(c[i] + 1))
continue;
tmp++;
L[tmp] = r[i] + 1;
R[tmp] = c[i] + 1;
} else {
if (st[c[i] + 1].count(r[i] + 1))
continue;
tmp++;
L[tmp] = c[i] + 1;
R[tmp] = r[i] + 1;
}
st[L[tmp]].insert(R[tmp]);
ar[++sz] = L[tmp];
ar[++sz] = R[tmp];
}
n = tmp;
sort(ar + 1, ar + sz + 1);
ll t = unique(ar + 1, ar + sz + 1) - ar - 1;
for (int i = 1; i <= n; i++) {
Lto[i] = lower_bound(ar + 1, ar + t + 1, L[i]) - ar;
Rto[i] = lower_bound(ar + 1, ar + t + 1, R[i]) - ar;
byl[Lto[i]].pb(i);
isworth[i] = true;
}
ll curmax = 0;
for (int i = 1; i <= 2 * n; i++) {
ll localmx = 0;
for (int to : byl[i]) {
localmx = max(localmx, Rto[to]);
if (Rto[to] <= curmax)
isworth[to] = false;
}
for (int to : byl[i])
if (Rto[to] < localmx)
isworth[to] = false;
curmax = max(curmax, localmx);
}
worth.pb({-1, -1, -1, -1});
for (int i = 1; i <= n; i++) {
if (isworth[i])
worth.pb({L[i], R[i], Lto[i], Rto[i]});
}
n = worth.size() - 1;
sort(worth.begin(), worth.end(), cmp);
ll L = 0, best = 0, R = maxR; //worth[worth.size() - 1].r * worth[worth.size() - 1].r;
ll M;
ll ans = inf;
while (L <= R) {
M = (L + R) / 2;
count(M, n);
if (cntt[n] > k) {
L = M + 1;
} else {
R = M - 1;
best = M;
}
}
count(best, n);
ans = dp[n] - cntt[n] * best;
return ans;
}
//main() {
// ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
// freopen("input.txt", "r", stdin);
// int n, m, k; vector <int> r, c;
// r.clear(); c.clear();
// cin >> n >> m >> k;
// for (int i = 1; i <= n; i++) {
// int x, y;
// cin >> x >> y;
//// cout << x << " " << y << endl;
// r.pb(x);
// c.pb(y);
// }
// cout << take_photos(n, m, k, r, c);
// return 0;
//}
