#include "aliens.h"
#include<algorithm>
#include<iostream>
#include<vector>
#include<stdio.h>
#include<queue>
using namespace std;
#define INF 1000000000000000000
typedef pair<long long int,long long int> pii;
typedef long long int lld;
vector<pair<long long int,long long int> >arr;
long long int DP[50001][4001];
int p;
lld sq(lld x){
return x*x;
}
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;
}
lld val(pii a, lld x){
return a.first*x+a.second;
}
bool useless(pii a, pii b, pii c){
if(c.first*a.second-c.second*a.first>=b.first*c.second-a.second*b.first+a.first*b.second-c.first*b.second)return true;
return false;
}
class CH{
deque<pii> d;
public:
void add(pii p){
if(d.size()<2){
d.push_back(p);return;
}
pii a,b;
bool B=true;
do{
a=d.back();d.pop_back();
b=d.back();
if(useless(b,a,p)){
}else{
B=false;
d.push_back(a);
}
}while(B && d.size()>=2);
d.push_back(p);
}
lld query(lld x){
lld ans=val(d.front(),x);
bool b=true;
while(b && d.size()>=2){
pii a=d.front();d.pop_front();
if(ans>val(d.front(),x)){
ans=val(d.front(),x);
}else{
b=false;
d.push_front(a);
}
}
return ans;
}
void clear(){
d.clear();
}
void size(){
cout<<d.size()<<endl;
}
void front(){
cout<<d.front().first<<" "<<d.front().second<<endl;
}
};
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;
}
}
lld penalty[p];
for(int i=1;i<p;i++){
penalty[i]=-sq2(arr[i-1].second-arr[i].first+1);
//cout<<penalty[i]<<endl;
}penalty[0]=0;
DP[0][0]=0;
long long int ans=INF;
CH *A;
A=new CH();
//A->add(pii(2*(-arr[0].first+1),sq(arr[0].first-1)));
//A->size();
for(int photo=1;photo<=k;photo++){
for(int i=0;i<p;i++){//A->front();
A->add(pii(2*(-arr[i].first+1),sq(-arr[i].first+1)+DP[i][photo-1]+penalty[i]));
if(i+1>=photo)DP[i+1][photo]=min(A->query(arr[i].second)+arr[i].second*arr[i].second,DP[i+1][photo]);
//A->front();
//cout<<arr[i].first<<" "<<arr[i].second<<" "<<A->query(arr[i].second)<<endl;
}//cout<<endl;
A->clear();
/*for(int i=0;i<=p;i++){
cout<<DP[i][photo]<<" "<<i<<" "<<photo<<endl;
}*/
}
for(int i=0;i<=k;i++)ans=min(ans,DP[p][i]);
return ans;
}
