#include "aliens.h"
#include <algorithm>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;
typedef __int128 ll;
const ll inf = 4e33;
struct line {
int k;
ll b;
int ops;
line(int k_, ll b_, int ops_) {
k = k_;
b = b_;
ops = ops_;
}
line() = default;
pair<ll, int> get(int x) {
return { k * 1ll * x + b, ops };
}
};
const int MAXN = 1e5 + 7;
int xs[MAXN];
const int sz = 1 << 20;
line tree[sz];
struct LiChao {
void upd(int v, int l, int r, line ln) {
int m = (l + r) / 2;
if (ln.get(xs[m]) < tree[v].get(xs[m])) {
swap(tree[v], ln);
}
if (r - l == 1) return;
if (ln.get(xs[l]) < tree[v].get(xs[l])) {
upd(v * 2, l, m, ln);
}
if (ln.get(xs[r - 1]) < tree[v].get(xs[r - 1])) {
upd(v * 2 + 1, m, r, ln);
}
}
pair<ll, int> get(int v, int l, int r, int qi) {
pair<ll, int> res = tree[v].get(xs[qi]);
if (r - l == 1) return res;
int m = (l + r) / 2;
if (qi < m) return min(res, get(v * 2, l, m, qi));
else return min(res, get(v * 2 + 1, m, r, qi));
}
int N;
void init(int n){
N = n;
for (int i = 0; i < 4 * n; ++i) {
tree[i] = line(0, inf, 0);
}
}
pair<ll, int> get(int x) {
return get(1, 0, N, lower_bound(xs, xs + N, x) - xs);
}
void upd(line ln) {
upd(1, 0, N, ln);
}
} tr;
vector<pair<ll, int>> dp;
pair<ll, int> calc(ll lambda, int n, vector<pair<int, int>> &st) {
tr.init(n);
for (int i = 0; i < n; ++i) {
tr.upd(line(-2ll * st[i].first, dp[i].first + st[i].first * 1ll * st[i].first, dp[i].second));
dp[i + 1] = tr.get(st[i].second + 1);
dp[i + 1].second++;
dp[i + 1].first += (st[i].second + 1) * 1ll * (st[i].second + 1) + lambda;
if (i < n - 1 && st[i].second >= st[i + 1].first) {
dp[i + 1].first -= (st[i].second - st[i + 1].first + 1) * 1ll * (st[i].second - st[i + 1].first + 1);
}
}
return dp[n];
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<pair<int, int>> a(n);
for (int i = 0; i < n; ++i) {
if (r[i] > c[i]) swap(r[i], c[i]);
a[i] = { r[i], c[i] };
}
sort(a.begin(), a.end(), [&](pair<int, int> x, pair<int, int> y) {
return pair<int, int>(x.second, x.first) < pair<int, int>(y.second, y.first);
});
vector<pair<int, int>> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && a[i].first <= st.back().first && a[i].second >= st.back().second) {
st.pop_back();
}
st.push_back(a[i]);
}
n = st.size();
dp.resize(n + 1);
dp[0] = { 0, 0 };
for (int j = 0; j < n; ++j) {
xs[j] = st[j].second + 1;
}
tr.init(n);
ll li = -1, ri = 1e20;
while (ri - li > 1) {
ll mi = (li + ri) / 2;
pair<ll, int> res = calc(mi, n, st);
if (res.second > k) {
li = mi;
}
else {
ri = mi;
}
}
pair<ll, int> res = calc(ri, n, st);
return res.first - res.second * ri;
}
