#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x),end(x)
struct Line {
mutable ll k, m, p;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
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()) { x->p = inf; return false; }
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) {
auto z = insert({k, m, 0}), 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));
}
ll query(ll x) { assert(!empty());
auto l = *lower_bound(x);
return l.k * x + l.m;
}
};
ll take_photos(int n, int m, int K, vector<int> r, vector<int> c) {
vector<pair<ll, ll>> intvs;
for (int i = 0; i < n; i++) {
intvs.emplace_back(min(r[i], c[i]), -max(r[i], c[i]));
}
sort(all(intvs));
vector<pair<ll, ll>> st;
for (auto [l, r] : intvs) {
if (st.empty() || -r > st.back().second)
st.emplace_back(l, -r);
}
//for (auto [l, r] : st) {
// cerr << "intv " << l << " " << r << "\n";
//}
constexpr ll inf = LLONG_MAX;
auto square = [&] (ll x) { return x * x; };
vector<vector<ll>> dp(st.size() + 1, vector<ll>(K + 1));
dp[st.size()][0] = 0;
for (ll i = (ll)st.size() - 1; i >= 0; i--)
dp[i][0] = inf;
for (ll remk = 1; remk <= K; remk++) {
dp[st.size()][remk] = 0;
LineContainer lc;
auto addToLC = [&] (ll ie) {
if (ie == 0) return;
if (dp[ie][remk - 1] == inf) return;
ll ex = st[ie-1].second + 1;
ll bx = st[ie].first;
ll k = -2 * ex;
ll m =
dp[ie][remk - 1]
+ square(ex)
- square(max(ex - bx, 0LL));
lc.add(-k, -m);
};
for (ll i = (ll)st.size() - 1; i >= 0; i--) {
ll ans = dp[st.size()][remk - 1] + square(st.back().second - st[i].first + 1);
/*for (ll ie = i + 1; ie < (ll)st.size(); ie++) {
ll ex = st[ie-1].second + 1;
ll bx = st[ie].first;
ans = min(ans,
dp[ie][remk - 1]
+ square(ex)
- 2 * ex * st[i].first
+ square(st[i].first)
- square(max(ex - bx, 0LL))
);
}*/
if (!lc.empty())
ans = min(ans, -lc.query(st[i].first) + square(st[i].first));
dp[i][remk] = ans;
addToLC(i);
}
}
return dp[0][K];
}
