//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;
const ll LLINF = (ll)1e18 + 10;
ve<pii> P;
ve<ll> L;
int a;
struct segment {
ll m, b, l, r, k;
};
double intersect(ll m1, ll m2, ll b1, ll b2) {
return (double) (b1 - b2) / (double) (m2 - m1);
}
ll sq(int x) { return (ll)x*x; }
pair<ll, ll> calc(ll lambda) {
ve<ll> DP(a), T(a);
list<segment> H;
DP[0] = sq(P[0].second - P[0].first + 1) + lambda;
T[0] = 1;
for (int i = 1; i < a; i++) {
ll x = -P[i].first + 1;
ll b = DP[i - 1] - L[i] + x * x;
ll m = 2 * x;
if (H.size() == 0) H.push_back({m, b, -LLINF, LLINF, T[i - 1]});
else {
while (intersect(H.back().m, m, H.back().b, b) < (double)H.back().l) {
H.pop_back();
}
double z = intersect(H.back().m, m, H.back().b, b);
ll l = (ll)ceil(z);
H.back().r = (ll)floor(z);
H.push_back({m, b, l, LLINF, T[i - 1]});
}
while (H.begin()->r < P[i].second) {
H.pop_front();
}
H.begin()->l = -LLINF;
ll q = H.begin()->m * P[i].second + H.begin()->b;
ll v = q + sq(P[i].second) + lambda;
DP[i] = sq(P[i].second - P[0].first + 1) + lambda;
T[i] = 1;
if (DP[i] > v) {
DP[i] = v;
T[i] = H.begin()->k + 1;
}
}
return {DP[a - 1], T[a - 1]};
}
ll take_photos(int n, int m, int k, ve<int> R, ve<int> C) {
map<int, int> M;
for (int i = 0; i < n; i++) {
int r = R[i];
int c = C[i];
if (c < r) swap(r, c);
if (M.find(r) == M.end()) M[r] = c;
else M[r] = max(M[r], c);
}
int cOld = -1;
a = 0;
for (pii p : M) {
int r, c;
tie(r, c) = p;
if (c > cOld) {
cOld = c;
P.push_back({r, c});
a++;
}
}
L = ve<ll>(a);
for (int i = 1; i < a; i++) {
if (P[i - 1].second >= P[i].first) {
L[i] = sq(P[i - 1].second - P[i].first + 1);
}
}
ll lo = 0;
ll hi = (ll)2e12;
ll v, t, mid;
while (lo < hi) {
mid = (lo + hi) / 2;
tie(v, t) = calc(mid);
if (t > min(a, k)) lo = mid + 1;
else if (t <= min(a, k)) hi = mid;
}
tie(v, t) = calc(lo);
return v - min(a, k) * lo;
}
