#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e12;
struct CHT {
struct line {
ll a, b, i;
ll f(ll x) { return a * x + b; };
};
ll intersect(line f1, line f2) {
assert(f1.a != f2.a);
return floor((f1.b - f2.b) / ((double)f2.a - f1.a));
}
vector<line> st;
vector<ll> p;
void insert(line t) {
if (st.empty()) {
st.push_back(t);
p.push_back(-INF);
return;
}
while (!st.empty() && intersect(st.back(), t) <= p.back()) {
p.pop_back();
st.pop_back();
}
p.push_back(intersect(st.back(), t));
st.push_back(t);
}
int opt = 0;
// for every 0 <= i < q x[i] < x[i+1]
line query(ll x) {
opt = min(opt, (int)st.size() - 1);
while (opt < (int)st.size() - 1 && p[opt + 1] <= x) opt++;
return st[opt];
}
};
template<typename T1, typename T2>
pair<T1, T2> operator + (pair<T1, T2> a, pair<T1, T2> b) {
return make_pair(a.first + b.first, a.second + b.second);
};
int n;
vector<long long> l;
vector<long long> r;
pair<long long, int> func(long long lambda) {
vector<pair<ll, int>> dp(n);
vector<ll> t(n);
for (int i = 0; i < n - 1; i++)
t[i] = max(0ll, r[i] - l[i + 1] + 1)
* max(0ll, r[i] - l[i + 1] + 1);
CHT convex;
for (int i = 0; i < n; i++) {
dp[i] = {(r[i] - l[0] + 1) * (r[i] - l[0] + 1), 1};
if (i) {
auto t = convex.query(r[i]);
dp[i] = min(dp[i], {t.f(r[i]) + r[i] * r[i], dp[t.i].second + 1});
}
ll a = -2 * (l[i+1] - 1);
ll b = (l[i+1] - 1) * (l[i+1] - 1) - t[i] + lambda + dp[i].first;
convex.insert({a, b, i});
}
return dp[n - 1];
}
long long take_photos(int _n, int m, int k, vector<int> _r, vector<int> _c) {
n = _n;
for (int i = 0; i < n; i++)
if (_r[i] > _c[i]) swap(_r[i], _c[i]);
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int a, int b) {
if (_r[a] == _r[b]) return _c[a] > _c[b];
return _r[a] < _r[b];
});
for (int cur : ord) {
if (r.empty() || r.back() < _c[cur]) {
l.push_back(_r[cur]);
r.push_back(_c[cur]);
}
}
n = (int)l.size();
long long lb = -1, rb = 1e13;
while (rb - lb > 1) {
long long mid = (lb + rb) / 2;
if (func(mid).second <= k)
rb = mid;
else
lb = mid;
}
assert(func(rb).second == k);
return func(rb).first - k * rb;
}
