#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 101010;
const int M = 1010101;
int n, m, k; pair<int, int> a[M];
vector<pair<int, int>> v;
struct cht {
vector<array<ll, 3>> cht;
int p = 0;
void init() {
p = 0;
vector<array<ll, 3>>().swap(cht);
}
// min-cht, decreasing s
void insert(ll s, ll t, int i) {
while (cht.size() >= 2) {
auto [ps, pt, _] = cht[cht.size() - 2];
auto [qs, qt, __] = cht.back();
if ((t - pt) * (ps - qs) <= (ps - s) * (qt - pt))
cht.pop_back();
else
break;
}
cht.push_back({s, t, i});
}
// increasing x
pair<ll, int> query(ll x) {
while (p + 1 < cht.size()) {
auto [ps, pt, _] = cht[p];
auto [qs, qt, __] = cht[p + 1];
if (x * (ps - qs) >= (qt - pt))
++p;
else
break;
}
return {x * cht[p][0] + cht[p][1], cht[p][2]};
}
} t1;
ll dp[N], bt[N];
pair<ll, ll> run(ll x) {
t1.init();
t1.insert(-4 * v[0].first, 2ll * v[0].first * v[0].first, 0);
for (int i = 1; i <= n; i++) {
auto [val, b] = t1.query(v[i - 1].second + 1);
dp[i] = val + 2ll * (v[i - 1].second + 1) * (v[i - 1].second + 1) + x;
bt[i] = b;
if (i != n) {
ll val = 2ll * v[i].first * v[i].first + dp[i];;
if (v[i - 1].second >= v[i].first)
val -= 2ll * (v[i - 1].second - v[i].first + 1) * (v[i - 1].second - v[i].first + 1);
t1.insert(-4 * v[i].first, val, i);
}
}
int cnt = 0;
for (int i = n; i != 0; i = bt[i])
++cnt;
return {dp[n], cnt};
}
ll take_photos(int _n, int _m, int _k, vector<int> _r, vector<int> _c) {
n = _m; m = _n; k = _k;
for (int i = 0; i < m; i++) {
if (_r[i] > _c[i])
swap(_r[i], _c[i]);
a[i] = {_r[i], _c[i]};
}
sort(a, a + m);
v.push_back(a[0]);
for (int i = 1; i < m; i++) {
if (v.back().second < a[i].second) {
if (v.back().first == a[i].first)
v.pop_back();
v.push_back(a[i]);
}
}
n = v.size();
// aliens trick
ll L = 0, R = 1e12 + 10;
while (L < R) {
ll M = (L + R) / 2;
if (run(2 * M + 1).second <= k)
R = M;
else
L = M + 1;
}
auto [x, y] = run(2 * L + 1);
return (x - (2 * L + 1) * y - 2 * L * (min(n, k) - y)) / 2;
}
