#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;
/**
* @brief Li Chao Tree with dynamically created nodes
*/
class li_chao_tree {
private:
struct line { int m; ll b; };
ll eval(const line &f, int x) { return (ll) f.m * x + f.b; }
struct node {
node *left, *right;
line f;
int l, r;
node(int _l, int _r) : l(_l), r(_r) {
left = right = nullptr;
f = {0, LINF};
}
} *root;
void add(node *cur, line nf) {
int m = (cur->l + cur->r) / 2;
bool bl = eval(nf, cur->l) < eval(cur->f, cur->l);
bool bm = eval(nf, m) < eval(cur->f, m);
if (bm) swap(cur->f, nf);
if (cur->r - cur->l == 1) return;
if (bl != bm) {
if (cur->left == nullptr) cur->left = new node(cur->l, m);
add(cur->left, nf);
} else {
if (cur->right == nullptr) cur->right = new node(m, cur->r);
add(cur->right, nf);
}
}
long long query(node *cur, int x) {
if (cur == nullptr) return LINF;
if (cur->r - cur->l == 1) return eval(cur->f, x);
int m = (cur->l + cur->r) / 2;
if (x < m) return min(eval(cur->f, x), query(cur->left, x));
else return min(eval(cur->f, x), query(cur->right, x));
}
public:
li_chao_tree(long long l, long long r) {
root = new node(l, r);
}
void add(int m, long long b) {
add(root, {m, b});
}
long long query(long long x) {
return query(root, x);
}
};
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<li_chao_tree> lct(k + 1, li_chao_tree(0, 0));
for (int j = 0; j <= k; j++) lct[j] = li_chao_tree(0, m + 5);
for (int j = 0; j < k; j++) lct[j].add(-2 * r[0], (ll) r[0] * r[0] - 2 * r[0]);
vll dp(k + 1, 0);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) dp[j] = lct[j - 1].query(c[i - 1]) + (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));
}
}
debug(dp);
return dp[k];
}
