#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "../debug.h"
#else
#define debug(...) 0
#endif
using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
const ll LINF = (ll) 1e18;
class convex_hull {
private:
vector<long long> a, b;
vector<int> id;
int ptr = 0;
int bad(int l1, int l2, long long _a, long long _b) {
if ((a[l1] == _a) && (b[l1] == _b)) return 1;
return ((_b - b[l1]) * (a[l1] - a[l2]) > (b[l2] - b[l1]) * (a[l1] - _a));
}
public:
void add(long long _a, long long _b, int _id) {
while ((int) a.size() >= 2 && bad((int) a.size() - 1, (int) a.size() - 2, _a, _b)) {
a.pop_back();
b.pop_back();
id.pop_back();
}
a.push_back(_a);
b.push_back(_b);
id.push_back(_id);
}
pair<int, long long> query(long long x) {
if (ptr >= (int) a.size()) {
ptr = (int) a.size() - 1;
}
while (ptr < (int) a.size() - 1 && a[ptr + 1] * x + b[ptr + 1] >= a[ptr] * x + b[ptr]) {
ptr++;
}
return {id[ptr], a[ptr] * x + b[ptr]};
}
};
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]);
vii segments;
for (int i = 0; i < n; i++) segments.push_back({r[i], c[i]});
sort(segments.begin(), segments.end(), [&](const ii &a, const ii &b) {
if (a.first == b.first) return a.second > b.second;
return a.first < b.first;
});
vi nr = {segments[0].first}, nc = {segments[0].second};
for (int i = 1; i < n; i++) {
if (!(nr.back() <= segments[i].first && segments[i].second <= nc.back())) {
nr.push_back(segments[i].first);
nc.push_back(segments[i].second);
}
}
swap(r, nr); swap(c, nc); n = (int) r.size();
debug(r, c);
//vector<vll> dp(n + 1, vll(k + 1, LINF)); dp[0].assign(k + 1, 0);
vector<convex_hull> lct(k + 1);
for (int j = 0; j < k; j++) lct[j].add(-(-2 * r[0]), -((ll) r[0] * r[0] - 2 * r[0]), -1);
vll dp(k + 1, 0); dp[0] = LINF;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) dp[j] = -lct[j - 1].query(c[i - 1]).second + (ll) (c[i - 1] + 1) * (ll) (c[i - 1] + 1);
if (i < n) for (int j = 0; j <= k; j++) {
lct[j].add(-(-2 * r[i]), -(dp[j] + (ll) r[i] * r[i] - 2 * r[i] - max(0ll, (ll) c[i - 1] - r[i] + 1) * max(0ll, (ll) c[i - 1] - r[i] + 1)), -1);
}
debug(dp);
}
return dp[k];
}
