#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
const long long maxn = 100005;
long long ans[maxn][2];
long long n,m,k;
vector <pair <long long,long long> > w,p;
bool cmp(pair <long long,long long> i, pair <long long,long long> j)
{
if(i.first==j.first)return i.second>j.second;
return i.first<j.first;
}
struct CVH
{
vector < pair <long long,long long> > lines;
vector <int> number;
long long px;
CVH()
{
lines.clear();
number.clear();
// lines.push_back({0,0});
px = 0;
}
double intersect( pair <long long, long long> l1, pair <long long,long long> l2)
{
return (double)(l2.second-l1.second)/(l1.first-l2.first);
}
void add_line(long long a, long long b, int key)
{
while(lines.size()>=2)
{
auto l1 = lines.back();
auto l2 = lines[lines.size()-2];
//if((l2.second-l1.first)*(l2.first-)
if(intersect(l1,l2)>intersect(l2,{a,b})){lines.pop_back();number.pop_back();}
else
break;
}
lines.push_back({a,b});
number.push_back(key);
}
pair < pair <long long,long long>, int> query(long long x)
{
//cout<<"HERE"<<endl;
//if(lines.size()==1)return {0,0};
while(px<lines.size()-1)
{
if(lines[px].first*x+lines[px].second>lines[px+1].first*x+lines[px+1].second)px++;
else
break;
}
//cout<<"FOUND"<<px<<endl;
return {lines[px],number[px]};
}
};
long long square(long long a)
{
return a*a;
}
long long ANS[maxn],keys[maxn];
pair <long long, int> solve(long long C){
CVH u = CVH();
//cout<<p[1].first<<"&&&&"<<p[1].second<<endl;
ANS[1] = square(p[1].second-p[1].first+1)+C;
keys[1] = 1;
long long M = -2*(p[2].first-1);
long long B = ANS[1] + (p[2].first-1)*(p[2].first-1)- (p.size()>2 ? max((long long) 0,p[1].second-p[1+1].first+1)* max((long long)0,p[1].second-p[1+1].first+1) : 0) ;
// cout<<M<<" "<<B<<endl;
u.add_line(M,B,1);
for(long long i=2;i<p.size();i++)
{
//cout <<" :: "<<i<<" :::: "<<p[i].first<<" "<<p[i].second<<endl;
auto z = u.query(p[i].second);
auto d = z.first;
auto r = z.second;
long long ans = d.first*p[i].second+d.second+p[i].second*p[i].second+C;
ANS[i] = ans;
keys[i] = keys[r]+1;
if(square(p[i].second-p[1].first+1)+C<=ANS[i]){ANS[i] = square(p[i].second-p[1].first+1)+C;keys[i]=1;}
if(i<p.size()-1){
long long M = -2*(p[i+1].first-1);
long long B = ANS[i] + (p[i+1].first-1)*(p[i+1].first-1) - max((long long) 0,p[i].second-p[i+1].first+1)* max((long long)0,p[i].second-p[i+1].first+1);
// cout<<M<<" "<<B<<endl;
u.add_line(M,B,i);}
// cout<<"&& "<<i<<" "<<ANS[i]<<" - "<<keys[i]<<endl;
}
return {ANS[p.size()-1],keys[p.size()-1]};
}
long long take_photos(int _n, int _m, int _k, std::vector<int> _r, std::vector<int> _c) {
n = _n;
m = _m;
k = _k;
w.resize(n);
long long i;
for(i=0;i<_r.size();i++)
{
_r[i]++;
_c[i]++;
w[i].first = min(_r[i],_c[i]);
w[i].second = max(_r[i],_c[i]);
}
sort(w.begin(),w.end(),cmp);
p.push_back({0,0});
for(i=0;i<n;i++)
{
if(p.back().first<=w[i].first&&w[i].second<=p.back().second)continue;
p.push_back(w[i]);
}
if(p.size()==2)
{
return square(p[1].second-p[1].first+1);
}
/*
long long uk1 = 0, uk2 = m*m,mid;
while(uk1<uk2)
{
mid = (uk1+uk2)/2;
cout<<"SOLVE WITH"<<" "<<mid<<endl;
auto p = solve(mid);
cout<<"solved: "<<p.first<<" "<<p.second<<endl;
if(p.second>k)uk1 = mid+1;
else
uk2 = mid;
}
// cout<<ANS[p.size()-1]<<endl;
return (ANS[p.size()-1]-k*uk2);
*/
long long uk1 = -1e12-7, uk2 = 1,mid;
k = min(k,(long long)p.size());
while(uk1<uk2)
{
mid = (uk1+uk2+1)/2;
//cout<<"SOLVE WITH"<<" "<<mid<<endl;
auto p = solve(-mid);
// cout<<"solved: "<<p.first<<" "<<p.second<<endl;
if(p.second>k)uk2 = mid-1;
else
uk1 = mid;
}
auto P = solve(-uk1);
// cout<<ANS[p.size()-1]<<endl;
return (ANS[p.size()-1]+k*uk1);
}
