#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll inf = 2e12;
struct Line {
mutable ll k, m, p, qtd;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
static 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()) return x->p = inf, 0;
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 qtd) {
auto z = insert({ k, m, 0, qtd }), 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));
}
pll query(ll x) {
assert(!empty());
auto l = *lower_bound(x);
return {l.k * x + l.m, l.qtd};
}
};
pair<ll, ll> solve(int n, vector<pair<ll, ll>> &ranges, ll x)
{
LineContainer lc;
vector<pll> dp(n+1, {0, 0});
for (int i=n-1; i>=0; i--) {
auto [li, ri] = ranges[i];
lc.add(2*(ri+1), -((ri+1)*(ri+1) + dp[i+1].first), dp[i+1].second);
auto [qry, jumps] = lc.query(li);
dp[i] = {li*li - qry + x, jumps+1};
if (i > 0 && ranges[i-1].second >= li) {
dp[i].first -= (ranges[i-1].second-li+1)*(ranges[i-1].second-li+1);
}
}
return dp[0];
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
vector<pair<ll, ll>> ranges, tmp;
for (int i=0; i<n; i++) {
tmp.push_back({min(r[i], c[i]), -max(r[i], c[i])});
}
sort(tmp.begin(), tmp.end());
for (auto [l, r]: tmp) {
if (ranges.empty() || ranges.back().second < -r) {
ranges.push_back({l, -r});
}
}
n = ranges.size();
k = min(k, n);
ll lo = -inf, hi = inf;
while (hi-lo > 1) {
ll mid = (lo+hi)/2;
auto [val, low] = solve(n, ranges, mid);
if (low < k) {
hi = mid;
} else {
lo = mid;
}
}
auto [val, low] = solve(n, ranges, lo);
return val - k*lo;
}
