#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first
#define sec second
const int N = 5e4 + 5, K = 1e2 + 5, M = 1e6 + 5, INF = 1e18, LG = 20;
int n, k;
arr<int, N> lf, rg, intr;
// Make lazy create
struct Lch {
int evl(pii x, int y) { return x.fir * y + x.sec; }
int nm;
arr<pii, 4 * N * LG> ln;
arr<int, 4 * N * LG> lf_ch, rg_ch;
void intl() {
for (int u = 1; u <= nm; u++)
ln[u] = {0, INF}, lf_ch[u] = rg_ch[u] = 0;
nm = 1;
ln[1] = {0, INF};
}
void prp(int u) {
if (!lf_ch[u]) lf_ch[u] = ++nm, rg_ch[u] = ++nm;
}
void ins(pii x, int u = 1, int lw = 0, int hg = M) {
int md = (lw + hg) / 2;
if (evl(x, md) < evl(ln[u], md)) swap(x, ln[u]);
if (lw == hg) return;
prp(u);
if (evl(x, lw) < evl(ln[u], lw)) ins(x, lf_ch[u], lw, md);
else ins(x, rg_ch[u], md + 1, hg);
}
int qry(int x, int u = 1, int lw = 0, int hg = M) {
if (lw == hg) return evl(ln[u], x);
int md = (lw + hg) / 2;
prp(u);
if (x <= md) return min(evl(ln[u], x), qry(x, lf_ch[u], lw, md));
return min(evl(ln[u], x), qry(x, rg_ch[u], md + 1, hg));
}
} lch;
arr<arr<int, K>, N> dp;
int sq(int x) { return x * x; }
void dp_cmp() {
lch.intl();
for (int i = 1; i <= n; i++)
dp[i][1] = sq(rg[i] - lf[1] + 1);
for (int c = 2; c <= k; c++) {
lch.intl();
for (int i = 1; i <= n; i++) {
dp[i][c] = sq(rg[i]) + 2 * rg[i] + 1 + lch.qry(rg[i]);
lch.ins({-2 * lf[i + 1], sq(lf[i + 1]) - 2 * lf[i + 1] - intr[i] + dp[i][c - 1]});
}
}
// for (int i = 1; i <= n; i++)
// for (int c = 1; c <= k; c++)
// cout << i << " " << c << ": " << dp[i][c] << endl;
}
map<int, int> rng;
int take_photos(signed _sz, signed _m, signed _k, vec<signed> _rw, vec<signed> _cl) {
k = _k; assert(k <= 100);
for (int i = 0; i < _sz; i++)
rng[min(_rw[i], _cl[i])] = max(rng[min(_rw[i], _cl[i])], (int) max(_rw[i], _cl[i]));
int mx_rg = -1;
vec<int> dlt;
for (pii x : rng) {
if (x.sec <= mx_rg) dlt.push_back(x.fir);
else mx_rg = x.sec;
}
for (int x : dlt) rng.erase(x);
while (rng.size()) {
pii x = *rng.begin(); rng.erase(rng.begin());
n++, lf[n] = x.fir, rg[n] = x.sec;
}
for (int i = 1; i <= n; i++) intr[i] = (rg[i] < lf[i + 1]) ? 0 : sq(rg[i] - lf[i + 1] + 1);
// cout << n << endl;
// for (int i = 1; i <= n; i++) cout << lf[i] << " " << rg[i] << endl;
dp_cmp();
int ans = *min_element(dp[n].begin() + 1, dp[n].begin() + k + 1);
return ans;
}
