#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define x first
#define y second
#define ii pair<ll,ll>
const ll inf=1e18+7;
ll n,m,k;
vector<ii>poll;
ll power(ll x)
{
return x*x;
}
struct node
{
ll x,y,num;
node(ll _x=0,ll _y=0,ll _num=0)
{
x=_x,y=_y,num=_num;
}
};
bool check(node a,node b,node c)
{
//double value_x=(b.y-a.y)/(a.x-b.x);
//double value_y=(c.y-b.y)/(b.x-c.x);
ll value_x=(b.y-a.y)*(b.x-c.x);
ll value_y=(c.y-b.y)*(a.x-b.x);
return (value_x>=value_y);
}
ii get(ll x,node need)
{
ii ans;
ans.x=need.x*x+need.y;
ans.y=need.num;
return ans;
}
ii getValue(ll C,deque<node>q)
{
int x=0;
int y=q.size()-1;
ii ans=get(C,q[0]);
while(x<y)
{
int mid=(x+y)/2;
ii ans_x=get(C,q[mid]);
ii ans_y=get(C,q[mid+1]);
if(ans_x>ans_y)x=mid+1;
else y=mid;
if(ans>ans_x)ans=ans_x;
if(ans>ans_y)ans=ans_y;
}
//cout<<ans.x<<" "<<ans.y<<endl;
return ans;
}
ii calc(ll constant)
{
ii trace=make_pair(0,0);
deque<node>convex;
for(ll i=n-1;i>=0;i--)
{
ll used=power(max((ll)0,poll[i].y-poll[i+1].x+1));
node path=node(-2*(poll[i].y+1),trace.x+power(poll[i].y+1)-used,trace.y);
while(convex.size()>=2&&!check(convex[convex.size()-2],convex[convex.size()-1],path))convex.pop_back();
convex.push_back(path);
ll C=poll[i].x;
ii need=getValue(C,convex);
//cout<<need.x<<" "<<need.y<<endl;
trace.x=need.x+power(poll[i].x)+constant;
trace.y=need.y+1;
//cout<<trace.x<<" "<<trace.y<<" "<<constant<<endl;
//cout<<trace.x<<" "<<trace.y<<" "<<power(poll[i].x)+constant<<" "<<need.x<<" "<<need.y<<endl;
}
return trace;
}
bool cmp(ii a,ii b)
{
if(a.x==b.x)return a.y>b.y;
return a.x<b.x;
}
ll take_photos(int _n,int _m,int _k,vector<int>r,vector<int>c)
{
n=_n;
m=_m;
k=_k;
vector<ii>block;
for(ll i=1;i<=n;i++)
{
ll x=min(r[i-1],c[i-1]);
ll y=max(r[i-1],c[i-1]);
block.push_back({x,y});
}
sort(block.begin(),block.end(),cmp);
block.resize(unique(block.begin(),block.end())-block.begin());
vector<ll>q;
for(ll i=n-1;i>=0;i--)
{
while(!q.empty()&&block[q.back()].y<=block[i].y)q.pop_back();
q.push_back(i);
}
reverse(q.begin(),q.end());
for(ll index:q)poll.push_back({block[index].x,block[index].y});
n=(ll)poll.size();
poll.push_back({m,m});
//for(ii node:poll)cout<<node.x<<" "<<node.y<<endl;
k=min(k,n);
ll x=0;
ll y=m*m+1;
ll res=m*m;
for(ll cnt=0;cnt<=50;cnt++)
{
ll mid=(x+y)/2;
ii ans=calc(mid);
if(ans.y<=k)
{
res=mid;
y=mid;
}
else x=mid;
}
ii ans=calc(res);
return ans.x-k*res;
}
