#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;
vector <vector <ll> > dp;
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 = -1;
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;
}
void calc(int id, int l, int r, int from, int to){
if (l > r)
return;
int mid = (l + r) >> 1;
int pos = -1;
dp[id][mid] = 2e18;
for(int i = from; i <= min(mid, to); i++)
if (dp[id][mid] > dp[id ^ 1][i - 1] + cost(i, mid)){
dp[id][mid] = dp[id ^ 1][i - 1] + cost(i, mid);
pos = i;
}
calc(id, l, mid - 1, from, pos);
calc(id, mid + 1, r, pos, to);
}
ll solve(){
segs.insert(segs.begin(), segment(-1, -1));
dp.resize(2, vector<ll>(n + 2, 2e18));
dp[0][0] = dp[1][0] = 0;
for(int i = 1; i <= n; i++)
dp[1][i] = cost(1, i);
for(int i = 2; i <= k; i++)
calc(i & 1, 1, n, 1, n);
return dp[k & 1][n];
}
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();
}
