#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = __int128_t;
#define all(x) begin(x),end(x)
struct Line {
mutable ll k, m, p;
ll howManyPhotos;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
const ll inf = LLONG_MAX;
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b);
}
bool isect(iterator x, iterator y) {
if (y == end()) { x->p = inf; return false; }
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m, ll howManyPhotos) {
auto z = insert({k, m, 0, howManyPhotos}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
}
pair<ll, ll> query(ll x) { assert(!empty());
auto l = *lower_bound(x);
return make_pair(l.k * x + l.m, l.howManyPhotos);
}
};
long long take_photos(int n, int m, int K, vector<int> r, vector<int> c) {
vector<pair<ll, ll>> intvs;
for (int i = 0; i < n; i++) {
intvs.emplace_back(min(r[i], c[i]), -max(r[i], c[i]));
}
sort(all(intvs));
vector<pair<ll, ll>> st;
for (auto [l, r] : intvs) {
if (st.empty() || -r > st.back().second)
st.emplace_back(l, -r);
}
//for (auto [l, r] : st) {
// cerr << "intv " << l << " " << r << "\n";
//}
auto square = [&] (ll x) { return x * x; };
auto alienTrick = [&] (ll cost) -> pair<ll, ll> { // (ans, howManyPhotos)
vector<pair<ll, ll>> dp(st.size() + 1);
dp[st.size()] = {0,0};
LineContainer lc;
auto addToLC = [&] (ll ie) {
if (ie == 0) return;
ll ex = st[ie-1].second + 1;
ll bx = st[ie].first;
ll k = -2 * ex;
ll m =
dp[ie].first
+ square(ex)
- square(max(ex - bx, (ll)0LL));
lc.add(-k, -m, dp[ie].second);
};
for (ll i = (ll)st.size() - 1; i >= 0; i--) {
pair<ll, ll> ans = {
dp[st.size()].first + square(st.back().second - st[i].first + 1) + cost,
-1LL
};
/*for (ll ie = i + 1; ie < (ll)st.size(); ie++) {
ll ex = st[ie-1].second + 1;
ll bx = st[ie].first;
ans = min(ans,
dp[ie][remk - 1]
+ square(ex)
- 2 * ex * st[i].first
+ square(st[i].first)
- square(max(ex - bx, 0LL))
);
}*/
if (!lc.empty()) {
auto lcq = lc.query(st[i].first);
ans = min(ans, make_pair(-lcq.first + square(st[i].first) + cost, lcq.second - 1));
}
dp[i] = ans;
addToLC(i);
}
return { dp[0].first, -dp[0].second };
};
ll lo = 0;
ll hi = m * m;
while (hi > lo) {
ll mid = lo + (hi - lo) / 2;
auto [ans, howManyPhotos] = alienTrick(mid);
if (howManyPhotos >= K)
lo = mid + 1;
else
hi = mid;
}
lo--;
auto [ans, howManyPhotos] = alienTrick(lo);
return ans - lo * K;
}
