#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 4e3 + 10;
const int MAXM = 1e6 + 10;
const long long INF = 1e18;
long long dp[MAXN][MAXN];
int seg[4 * MAXM];
struct interval{
int l, r;
interval(int _l = 0, int _r = 0){
l = _l, r = _r;
if(l > r) swap(l, r);
}
bool operator < (interval a){
if(r == a.r) return l > a.l;
return r < a.r;
}
};
void build(int pos, int ini, int fim){
seg[pos] = -1;
if(ini == fim) return;
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
build(e, ini, mid);
build(d, mid + 1, fim);
}
void update(int pos, int ini, int fim, int p, int q, int val){
if(ini > q || fim < p) return;
if(ini >= p && fim <= q){
seg[pos] = max(seg[pos], val);
return;
}
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
update(e, ini, mid, p, q, val);
update(d, mid + 1, fim, p, q, val);
}
int query(int pos, int ini, int fim, int id){
if(ini > id || fim < id) return -1;
if(ini == fim) return seg[pos];
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
return max(seg[pos], max(query(e, ini, mid, id), query(d, mid + 1, fim, id)));
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
vector<interval> ord (n);
for(int i = 0; i < n; i++)
ord[i] = interval(r[i], c[i]);
sort(ord.begin(), ord.end());
int minL = m;
for(int i = 0; i < n; i++){
minL = min(minL, ord[i].l);
dp[i][0] = (long long)(ord[i].r - minL + 1) * (ord[i].r - minL + 1);
}
int lAux[n][n];
build(1, 0, m);
for(int i = 0; i < n; i++){
for(int j = 0; j <= i; j++)
lAux[j][i] = query(1, 0, m, ord[j].l);
update(1, 0, m, ord[i].l + 1, m, i);
}
for(int j = 1; j < k; j++){
for(int i = 0; i < n; i++){
dp[i][j] = dp[i][j - 1];
for(int l = 0; l <= i; l++){
if(ord[l].l > ord[i].l) continue;
int h = lAux[l][i];
long long quad = (long long) (ord[i].r - ord[l].l + 1) * (ord[i].r - ord[l].l + 1);
long long minus = ((h < 0 || ord[h].r < ord[l].l) ? 0 : ((long long) (ord[h].r - ord[l].l + 1) * (ord[h].r - ord[l].l + 1)));
long long aux = quad + ((h < 0) ? 0 : dp[h][j - 1] - minus);
dp[i][j] = min(dp[i][j], aux);
}
}
}
return dp[n - 1][k - 1];
}
