#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];
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);
long long dif1, dif2;
dp[0][0]=0;
for (int i=1;i<=n;i++) {
dp[i][0]=INF;
for (int j=1;j<=k;j++) {
dp[i][j]=dp[i][j-1];
for (int p=i;p>=1;p--) {
dif1=a[i].r-a[p].l+1;
dif2=a[p-1].r-a[p].l+1;
if (dif2<0) dif2=0;
dp[i][j]=min(dp[i][j],dp[p-1][j-1]+dif1*dif1-dif2*dif2);
}
}
}
return dp[n][k];
}
