#include "aliens.h"
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN=1e5+10;
const long long INF=1e15;
struct Interval {
int l;
int r;
bool friend operator < (Interval a, Interval b) {
if (a.l==b.l) return a.r>b.r;
return a.l<b.l;
}
};
Interval b[MAXN];
vector <Interval> a;
vector <long long> dp[MAXN];
void dnc(int k, int l, int r, int opl, int opr) {
if (l>r) return;
int mid=(l+r)/2;
dp[mid][k]=INF;
int curop=-1;
long long dif1, dif2;
for (int i=opl;i<=min(mid,opr);i++) {
dif1=a[mid].r-a[i].l+1;
dif2=a[i-1].r-a[i].l+1;
if (dif2<0) dif2=0;
if (dp[mid][k]>dp[i-1][k-1]+dif1*dif1-dif2*dif2) {
dp[mid][k]=dp[i-1][k-1]+dif1*dif1-dif2*dif2;
curop=i;
}
}
//cout << l << ' ' << r << ' ' << mid << ' ' << dp[mid][k] << ' ' << curop << endl;
dnc(k,l,mid-1,opl,curop);
dnc(k,mid+1,r,curop,opr);
}
long long take_photos(int n, int m, int k, vector <int> r, vector <int> c) {
for (int i=0;i<n;i++) {
b[i].l=min(r[i],c[i]);
b[i].r=max(r[i],c[i]);
}
sort(b,b+n);
int maxr=b[0].r;
a.push_back({-1,-1});
a.push_back(b[0]);
for (int i=1;i<n;i++) {
if (b[i].r<=maxr) continue;
a.push_back(b[i]);
maxr=b[i].r;
}
n=a.size()-1;
k=min(n,k);
for (int i=0;i<=n;i++) dp[i].resize(k+1);
for (int i=1;i<=n;i++) dp[i][0]=INF;
dp[0][0]=0;
for (int i=1;i<=k;i++) {
dnc(i,1,n,1,n);
}
return dp[n][k];
}
