#include "aliens.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define pl pair < ll, ll >
#define vl vector < ll >
const int N = 5e4 + 7;
const ll INF = 1e18 + 7;
vector < vl > dp;
pl t[N], s[N];
ll rect (ll l, ll r){
if (l > r)
return 0LL;
return (r - l + 1) * (r - l + 1);
}
ll cost (ll j, ll i){
return rect(s[j].fr, s[i].sc) - rect(s[j].fr, s[j - 1].sc);
}
void divide (int l, int r, int optl, int optr, int j){
if (l > r)
return;
int mid = (l + r) >> 1, opt = 0;
for (int c = optl; c <= optr; c++){
if (dp[mid][j] > dp[c - 1][j - 1] + cost(c, mid)){
dp[mid][j] = min(dp[mid][j], dp[c - 1][j - 1] + cost(c, mid));
opt = c;
}
}
divide(l, mid - 1, optl, opt, j);
divide(mid + 1, r, opt, optr, j);
}
bool comp (pl a, pl b){
if (a.fr == b.fr)
return a.sc > b.sc;
return a.fr < b.fr;
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
dp.resize(n + 1);
for (int j = 0; j <= k; j++)
dp[0].pb(0);
for (int i = 1; i <= n; i++){
dp[i].pb(0);
for (int j = 1; j <= k; j++)
dp[i].pb(INF);
}
for (int i = 0; i < n; i++)
t[i + 1] = {min(r[i] + 1, c[i] + 1), max(r[i] + 1, c[i] + 1)};
sort(t + 1, t + n + 1, comp);
ll last = 0;
int x = 0;
for (int i = 1; i <= n; i++){
if (t[i].sc > last){
last = t[i].sc;
s[++x] = t[i];
}
}
n = x;
for (int i = 1; i <= n; i++)
dp[i][1] = cost(1, i);
for (int j = 2; j <= k; j++)
divide(1, n, 1, n, j);
return dp[n][k];
}
