#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
struct line
{
long long a,b,id;
line(){}
line(long long _a,long long _b,int _id)
{
a=_a;
b=_b;
id=_id;
}
long long data(long long x)
{
return a*x+b;
}
};
deque<line> cht,cht2;
int num;
pair<int,int> p[200001];
bool cmp(pair<int,int> p1,pair<int,int> p2)
{
if(p1.second==p2.second)return p1.first<p2.first;
return p1.second<p2.second;
}
long long sq(long long x)
{
return x*x;
}
double pt(line l1,line l2)
{
return (double)(l2.b-l1.b)/(double)(l1.a-l2.a);
}
void insert_(line l)
{
//cout<<l.a<<" - "<<l.b<<endl;
//while(cht2.size()>=2&&pt(cht2[cht2.size()-1],l)<pt(cht2[cht2.size()-2],l))cht2.pop_back();
cht2.push_back(l);
}
long long value(long long x,int id)
{
long long ans=1e18;
for(int i=0;i<cht.size();i++)
if(cht[i].id<id)
{
//cout<<cht[i].data(x)<<" ";
ans=min(ans,cht[i].data(x));
}
//cout<<endl;
return ans;
}
long long dp[200001];
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c)
{
for(int i=0; i<n; i++)
p[i]= {min(r[i],c[i]),max(r[i],c[i])};
sort(p,p+n,cmp);
for(int i=0; i<n; i++)
{
if(i!=0&&p[i].second==p[i-1].second)continue;
while(num!=0&&p[num-1].first>=p[i].first)num--;
p[num++]=p[i];
}
long long ans=1e18;
/*for(int i=0;i<num;i++)
{
dp[i][1]=sq(p[i].second-p[0].first+1);
if(i==num-1)ans=min(ans,dp[i][1]);
for(int j=2;j<=k;j++)
{
dp[i][j]=1e18;
for(int l=1;l<=i;l++)
{
//dp[i][j]=min(dp[i][j],dp[l-1][j-1]+sq(p[i].second-p[l].first+1)-sq(max(0,p[l-1].second-p[l].first+1)));
dp[i][j]=min(dp[i][j],sq(p[i].second+1)+
(p[l].first*(-2)*p[i].second-2*p[l].first+dp[l-1][j-1]-sq(max(0,p[l-1].second-p[l].first+1))+sq(p[l].first)));
}
if(i==num-1)ans=min(ans,dp[i][j]);
}
}*/
for(int i=0;i<num;i++)
{
dp[i]=sq(p[i].second-p[0].first+1);
long long b=-2*p[i+1].first+dp[i]-sq(max(0,p[i].second-p[i+1].first+1))+sq(p[i+1].first);
insert_({-2*p[i+1].first,b,i});
}
ans=dp[num-1];
cht=cht2;
cht2.clear();
for(int j=2;j<=k;j++)
{
for(int i=0;i<num;i++)
{
dp[i]=sq(p[i].second+1)+value(p[i].second,i);
long long b=-2*p[i+1].first+dp[i]-sq(max(0,p[i].second-p[i+1].first+1))+sq(p[i+1].first);
if(i!=num-1)insert_({-2*p[i+1].first,b,i});
//cout<<dp[i]<<" ";
}
//cout<<endl;
ans=min(ans,dp[num-1]);
cht=cht2;
cht2.clear();
}
return ans;
}
/*
long long value(long long x,int id)
{
if(cht.size()==1)return cht[0].data(x);
long long ans=1e18;
int l=0,r=cht.size()-2;
while(l<=r)
{
int m=(l+r)/2;
if(cht[m].id>=id)
{
r=m-1;
}
else
{
if(cht[m].data(x)<cht[m+1].data(x))
{
ans=cht[m].data(x);
r=m-1;
}
else
{
ans=cht[m+1].data(x);
l=m+2;
}
}
}
return ans;
}
*/
