#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000005;
struct Line {
long long k, n;
int cnt;
Line() {}
Line(long long _k, long long _n, int _cnt) : k(_k), n(_n), cnt(_cnt) {}
long long get(int x) {
return k * (long long) x + n;
}
};
int root, ls[4 * MAX], rs[4 * MAX], tsz;
Line st[4 * MAX];
void modify(int& node, int l, int r, Line k) {
if (!node) {
node = ++tsz;
st[node] = k;
return;
}
long long a = st[node].get(l);
long long b = k.get(l);
long long c = st[node].get(r);
long long d = k.get(r);
if (a >= b && c >= d) {
return;
}
if (a <= b && c <= d) {
st[node] = k;
return;
}
int mid = l + r >> 1;
if (a < b) {
swap(st[node], k);
}
if (st[node].get(mid) > k.get(mid)) {
modify(rs[node], mid + 1, r, k);
} else {
swap(st[node], k);
modify(ls[node], l, mid, k);
}
}
pair<long long, int> query(int node, int l, int r, int i) {
if (!node) {
return make_pair((long long) -1e18, -1e9);
}
if (l == r) {
return make_pair(st[node].get(i), st[node].cnt);
}
auto val = make_pair(st[node].get(i), st[node].cnt);
int mid = l + r >> 1;
if (i <= mid) {
val = max(val, query(ls[node], l, mid, i));
} else {
val = max(val, query(rs[node], mid + 1, r, i));
}
return val;
}
void build() {
for (int i = 1; i <= tsz; i++) {
ls[i] = 0;
rs[i] = 0;
}
root = 0;
tsz = 0;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
for (int i = 0; i < n; i++) {
if (r[i] > c[i]) {
swap(r[i], c[i]);
}
}
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
if (r[i] != r[j]) {
return r[i] < r[j];
} else {
return c[i] > c[j];
}
});
vector<pair<int, int>> pts;
int mx = -1;
for (int id = 0; id < n; id++) {
int i = order[id];
if (c[i] <= mx) {
continue;
} else {
mx = max(mx, c[i]);
pts.emplace_back(r[i], c[i]);
}
}
n = (int) pts.size();
k = min(k, n);
for (int i = 0; i < n; i++) {
r[i] = pts[i].first;
c[i] = pts[i].second;
}
vector<long long> w(n);
for (int i = 1; i < n; i++) {
long long d = c[i - 1] - r[i] + 1;
if (d < 0) {
continue;
}
w[i - 1] = d * d;
}
auto Solve = [&](long long cost) {
build();
vector<long long> dp(n);
vector<int> cnt(n);
for (int i = 0; i < n; i++) {
long long ft = 0;
int fc = 0;
if (i > 0) {
ft = dp[i - 1] - w[i - 1];
fc = cnt[i - 1];
}
modify(root, 0, MAX, Line(2 * r[i], -(r[i] * 1LL * r[i] + ft), -fc));
auto it = query(root, 0, MAX, c[i] + 1);
long long cs = -it.first + (c[i] + 1) * 1LL * (c[i] + 1);
dp[i] = cs + cost;
cnt[i] = -it.second + 1;
}
return make_pair(dp[n - 1], cnt[n - 1]);
};
long long low = 0, high = m * 1LL * m, ans = 0;
while (low <= high) {
long long mid = (low + high) >> 1;
auto cs = Solve(mid);
if (cs.second <= k) {
high = mid - 1;
ans = mid;
} else {
low = mid + 1;
}
}
return Solve(ans).first - ans * k;
}
