#include "aliens.h"
#include<algorithm>
#include<iostream>
#include<vector>
#include<stdio.h>
using namespace std;
#define INF 1000000000000000000
typedef pair<long long int,long long int> pii;
vector<pair<long long int,long long int> >arr;
long long int DP[50001][4001];
int p;
long long sq2(long long x){
if(x>0)return x*x;
return 0;
}
bool cmp(pii a, pii b){
if(a.first==b.first){
if(a.second>b.second)return true;
return false;
}
if(a.first<b.first)return true;
return false;
}
long long int min(long long int a, long long int b){
if(a<b)return a;
return b;
}
long long int computecost(int i, int j){
if(j<i)return 0;
long long int R=arr[j].second-arr[i].first+1;
R*=R;
if(i>0){
R-=sq2(arr[i-1].second-arr[i].first+1);
}
return R;
}
void compute(int x, int y, int photos, int a, int b){
if(x>y)return;
int mid=(x+y)/2;
int best=-1;
for(int i=a;i<=b;i++){
long long int can=DP[i][photos-1]+computecost(i,mid-1);
if(DP[mid][photos]>can){
best=i;
DP[mid][photos]=can;
}
}
compute(x,mid-1,photos,a,best);
compute(mid+1,y,photos,best,b);
}
long long take_photos(int n, int m, int k, vector<int> r,vector<int> c) {
pair<long long int,long long int>points[n];
for(int i=0;i<n;i++){
points[i]=pair<long long int,long long int>(r[i],c[i]);
if(r[i]>c[i])swap(points[i].first,points[i].second);
}
sort(points,points+n,cmp);
long long int cnt=-1;
for(int i=0;i<n;i++){
if(points[i].second>cnt){
cnt=points[i].second;
arr.push_back(points[i]);
}
}
p=arr.size();
for(int i=0;i<=k;i++){
for(int j=0;j<=p;j++){
DP[j][i]=INF;
}
}
DP[0][0]=0;
long long int ans=INF;
for(int photo=1;photo<=k && photo<=p;photo++){
compute(0,p,photo,0,p);
ans=min(ans,DP[p][photo]);
}
return ans;
}
