#include "aliens.h"
#include<algorithm>
#include<iostream>
#include<vector>
#include<stdio.h>
#include<queue>
#include<deque>
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 Cost[1000000];
lld sq(lld x){
return x*x;
}
lld sq2(lld x){
if(x>0)return x*x;
return 0;
}
void print(pii a){
cout<<a.first<<" "<<a.second<<endl;
}
class CH{
deque<pii>d;
public:
double intersect(pii a,pii b){
return (double)(b.second-a.second)/(a.first-b.first);
}
void Print(){
queue<pii> q;
while(!d.empty()){
print(d.front());
q.push(d.front());
d.pop_front();
}
while(!q.empty()){
d.push_back(q.front());
q.pop();
}
}
void add(pii A){//print(A);
//cout<<d.size()<<endl;
if(d.size()<2){
d.push_back(A);
return;
}
pii B,C;
do{
B=d.back();
d.pop_back();
C=d.back();
}while(d.size()>1 && intersect(A,B)<=intersect(B,C));
if(intersect(A,B)>intersect(B,C)){
d.push_back(B);
}
d.push_back(A);
}
lld query(lld x){
if(d.size()==1)return d.front().first*x+d.front().second;
pii A,B;
do{
A=d.front();
d.pop_front();
B=d.front();
}while(d.size()>1 && intersect(A,B)<=x);
if(intersect(A,B)>x)d.push_front(A);
return d.front().first*x+d.front().second;
}
};
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);
}
for(int i=0;i<n;i++)points[i].second=-points[i].second;
sort(points,points+n);
for(int i=0;i<n;i++)points[i].second=-points[i].second;
long long int cnts=-1;
lld cntf=-1;
for(int i=0;i<n;i++){
if(points[i].second>cnts && points[i].first>cntf){
cnts=points[i].second;
cntf=points[i].first;
arr.push_back(points[i]);
//print(points[i]);
}
}
p=arr.size();
for(int i=0;i<p;i++){
if(i==0)Cost[i]=0;
else{
Cost[i]=sq2(-arr[i].first+arr[i-1].second+1);
}//cout<<Cost[i]<<endl;
}
lld DP[p+1][k+1];
for(int photo=0;photo<=k;photo++){
for(int i=0;i<=p;i++){
DP[i][photo]=INF;
}
}DP[0][0]=0;
for(int photo=1;photo<=k;photo++){
CH *C=new CH();
DP[0][photo]=0;
for(int i=1;i<=p;i++){
if(DP[i-1][photo-1]<INF){
C->add(pii(-2*arr[i-1].first+2,sq(arr[i-1].first-1)-Cost[i-1]+DP[i-1][photo-1]));
}
DP[i][photo]=min(DP[i][photo],DP[i][photo-1]);
/*for(int j=0;j<i;j++){
DP[i][photo]=min(DP[i][photo],DP[j][photo-1]-Cost[j]+sq(arr[i-1].second-arr[j].first+1));
}*/
DP[i][photo]=min(DP[i][photo],sq(arr[i-1].second)+C->query(arr[i-1].second));
//cout<<sq(arr[i-1].second)+C->query(arr[i-1].second)<<" "<<DP[i][photo]<<endl;
//C->Print();
//cout<<endl;
}
}
/*for(int photo=0;photo<=k;photo++){
for(int i=0;i<=p;i++){
cout<<DP[i][photo]<<" ";
}cout<<endl;
}*/
/*CH *D=new CH();
D->add(pii(2,1));
D->add(pii(-2,1));
D->add(pii(-3,2));D->Print();
D->add(pii(-4,3));
D->Print();*/
return DP[p][k];
}
