#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segment{
int l, r;
segment(int _l, int _r){
l = _l;
r = _r;
}
};
int n, m, k;
vector <segment> segs;
void prepare(){
sort(segs.begin(), segs.end(), [](const segment &a, const segment &b){
if (a.l != b.l)
return a.l < b.l;
return a.r > b.r;
});
vector <segment> tmp;
int maxR = 0;
for(segment s : segs){
if (s.r > maxR)
tmp.push_back(s);
maxR = max(maxR, s.r);
}
segs = tmp;
n = segs.size();
}
ll cost(int l, int r){
assert(l <= r || l > 0);
int w = segs[r].r - segs[l].l + 1;
int intersect = max(0, segs[l - 1].r - segs[l].l + 1);
return (ll) w * w - (ll) intersect * intersect;
}
ll solve(){
vector <vector <ll> > dp(n + 2, vector<ll>(k + 1, 2e18));
vector <vector <int> > pos(n + 2, vector<int>(k + 1, 0));
segs.insert(segs.begin(), segment(-1, -1));
for(int j = 0; j <= k; j++){
dp[0][j] = 0;
pos[n + 1][j] = n;
}
for(int i = 1; i <= n; i++){
pos[i][1] = 1;
dp[i][1] = cost(1, i);
}
for(int j = 2; j <= k; j++)
for(int i = n; i >= 1; i--)
for(int u = pos[i][j - 1]; u <= min(i, pos[i + 1][j]); u++)
if (dp[i][j] > dp[u - 1][j - 1] + cost(u, i)){
dp[i][j] = dp[u - 1][j - 1] + cost(u, i);
pos[i][j] = u;
}
return dp[n][k];
}
ll take_photos(int _n, int _m, int _k, vector<int> r, vector<int> c){
n = _n;
m = _m;
k = _k;
for(int i = 0; i < n; i++)
segs.push_back(segment(min(r[i], c[i]), max(r[i], c[i])));
prepare();
return solve();
}
