#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
#define sz(s) (int)s.size()
#define mem(a,i) memset(a,i,sizeof(a))
#define pb push_back
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define ll long long
#define F first
#define S second
#define ld long double
#define ppb pop_back
const int MAX=1e6+10;
const ll inf=2e18;
vector<int> vec[MAX];
vector<pair<ll,ll>> dp;
int n,m,k;
ll S(int x,int y){
ll a=x-y+1;
if(a<=0)return 0;
return a*a;
}
ld inter(pair<ll,ll> a,pair<ll,ll> b){
return (0.0+a.S-b.S)/(0.0+b.F-a.F);
}
struct cht{
vector<pair<pair<ll,ll>,ll>> lines;
int pos;
void init(){
lines.clear();
pos=0;
}
void add(ll k,ll x,ll cnt){
if(!lines.empty())assert(lines.back().F.F!=k);
while(sz(lines)>1&&inter(lines[sz(lines)-2].F,lines.back().F)>=inter(lines[sz(lines)-2].F,{k,x}))lines.ppb();
lines.pb({{k,x},cnt});
pos=min(pos,sz(lines)-1);
}
ll get(pair<ll,ll> a,ll x){
return a.F*x+a.S;
}
pair<ll,ll> get(ll x){
while(pos+1<sz(lines)&&get(lines[pos].F,x)>get(lines[pos+1].F,x)){
pos++;
}
return {get(lines[pos].F,x),lines[pos].S};
}
}C;
vector<pii> pts;
int check(ll c){
C.init();
for(int i=0;i<n;i++){
if(i-1>=0)C.add(-2*pts[i].S,dp[i-1].F+pts[i].S*1ll*pts[i].S-2*pts[i].S,dp[i-1].S);
else C.add(-2*pts[i].S,pts[i].S*1ll*pts[i].S-2*pts[i].S,0);
dp[i]={C.get(pts[i].F).F+pts[i].F*1ll*pts[i].F+2*pts[i].F+1+c,C.get(pts[i].F).S+1};
if(i!=n-1){
dp[i].F-=S(pts[i].F,pts[i+1].S);
}
}
return dp[n-1].S;
}
long long take_photos(int N, int M, int K, vector<int> r, vector<int> c) {
n=N,m=M,k=K;
for(int i=0;i<n;i++){
if(r[i]<c[i]){
swap(c[i],r[i]);
}
vec[r[i]].pb(c[i]);
}
for(int i=0;i<m;i++)sort(all(vec[i]));
stack<int> st;
for(int i=0;i<m;i++){
if(vec[i].empty())continue;
while(!st.empty()&&vec[st.top()][0]>=vec[i][0]){
st.pop();
}
st.push(i);
}
while(!st.empty()){
int x=st.top();
pts.pb({x,vec[x][0]});
st.pop();
}
reverse(all(pts));
n=sz(pts);
if(k>=n){
ll ans=0;
for(int i=0;i<n;i++){
ans+=S(pts[i].F,pts[i].S);
if(i!=n-1)ans-=S(pts[i].F,pts[i+1].S);
}
return ans;
}
dp.resize(n);
ll res=1e13;
for(ll l=0,r=1e13;l<=r;){
ll m=(l+r)/2;
// cout<<m<<" "<<check(m)<<"\n";
if(check(m)<=k){
r=m-1;
res=m;
}
else{
l=m+1;
}
}
//36 749999988180
// check(-1e8);
// cout<<n<<" "<<check(-1e8)<<" "<<check(0)<<" "<<check(res)<<" "<<check(1e13)<<"\n";
// cout<<res<<"\n";
// cout<<check(36)<<"\n";
check(res);
// cout<<dp[n-1].F<<" "<<dp[n-1].S<<" "<<res<<"\n";
return dp[n-1].F-k*res;
}
