#include "aliens.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define f first
#define se second
//#define int long long
#define pll pair<ll, ll>
#define pii pair<int, int>
using namespace std;
//const int N = 2e5 + 123;
const int N = 3e3 + 123;
const int M = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll inf = 1e16;
struct segment{
ll l, r, l1, r1;
segment(ll l, ll r, ll l1, ll r1) : l(l), r(r), l1(l1), r1(r1) {};
};
ll L[N], R[N], Lto[N], Rto[N], ar[N], sz = 0;
bool isworth[N];
vector <segment> worth;
vector <ll> byl[N];
unordered_set <ll> st[M];
ll dp[N][N];
bool cmp(segment x, segment y) {
return x.r < y.r;
}
ll cost(ll l, ll r) {
if (l > r)
return 0;
return (r - l + 1) * (r - l + 1);
}
ll take_photos(int n, int m, int k, vector <int> r, vector <int> c) {
if (n > 505 || m > 1005)
return 0;
int tmp = 0;
for (int i = 0; i < n; i++) {
if (c[i] >= r[i]) {
if (st[r[i] + 1].count(c[i] + 1))
continue;
tmp++;
L[tmp] = r[i] + 1;
R[tmp] = c[i] + 1;
} else {
if (st[c[i] + 1].count(r[i] + 1))
continue;
tmp++;
L[tmp] = c[i] + 1;
R[tmp] = r[i] + 1;
}
// if (L[tmp] == 4 && R[tmp] == 5) {
// cout << i << " " << r[i] + 1 << " " << c[i] + 1 << endl;
// cout << endl;
// }
st[L[tmp]].insert(R[tmp]);
ar[++sz] = L[tmp];
ar[++sz] = R[tmp];
}
n = tmp;
// for (int i = 1; i <= n; i++)
// cout << i << " " << L[i] << " " << R[i] << endl;
// cout << endl;
sort(ar + 1, ar + sz + 1);
ll t = unique(ar + 1, ar + sz + 1) - ar - 1;
for (int i = 1; i <= n; i++) {
Lto[i] = lower_bound(ar + 1, ar + t + 1, L[i]) - ar;
Rto[i] = lower_bound(ar + 1, ar + t + 1, R[i]) - ar;
byl[Lto[i]].pb(i);
isworth[i] = true;
}
ll curmax = 0;
for (int i = 1; i <= 2 * n; i++) {
ll localmx = 0;
for (int to : byl[i]) {
localmx = max(localmx, Rto[to]);
if (Rto[to] <= curmax)
isworth[to] = false;
}
for (int to : byl[i])
if (Rto[to] < localmx)
isworth[to] = false;
curmax = max(curmax, localmx);
}
// for (int i = 1; i <= n; i++)
// cout << i << " " << isworth[i] << endl;
worth.pb({-1, -1, -1, -1});
for (int i = 1; i <= n; i++) {
if (isworth[i])
worth.pb({L[i], R[i], Lto[i], Rto[i]});
}
n = worth.size() - 1;
sort(worth.begin(), worth.end(), cmp);
for (int i = 1; i <= n; i++)
dp[1][i] = cost(worth[1].l, worth[i].r);
ll ans = dp[1][n];
for (int x = 2; x <= min(n, k); x++) {
for (int i = 1; i < k; i++)
dp[x][i] = inf;
for (int i = k; i <= n; i++) {
dp[x][i] = inf;
for (int j = 1; j < i; j++)
dp[x][i] = min(dp[x][i], dp[x - 1][j] + cost(worth[j + 1].l, worth[i].r) - cost(worth[j + 1].l, worth[j].r));
}
ans = min(ans, dp[x][n]);
}
return ans;
}
//main() {
// ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
// freopen("input.txt", "r", stdin);
// int n, m, k; vector <int> r, c;
// r.clear(); c.clear();
// cin >> n >> m >> k;
// for (int i = 1; i <= n; i++) {
// int x, y;
// cin >> x >> y;
//// cout << x << " " << y << endl;
// r.pb(x);
// c.pb(y);
// }
// cout << take_photos(n, m, k, r, c);
// return 0;
//}
