#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=4e18;
vector<int> vec[MAX];
vector<pair<ld,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<ld,ld> a,pair<ld,ld> b){
return (a.S-b.S)/(b.F-a.F);
}
struct cht{
vector<pair<pair<ld,ld>,ll>> lines;
int pos;
void init(){
lines.clear();
pos=0;
}
void add(ld k,ld x,ll cnt){
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);
}
ld get(pair<ld,ld> a,ld x){
return a.F*x+a.S;
}
pair<ld,ll> get(ld x){
if(lines.empty()){
return {inf,inf};
}
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(ld c){
C.init();
for(int i=0;i<n;i++)dp[i].F=inf,dp[i].S=0;
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);
}
// dp[i].F=min(dp[i].F,inf);
}
// cout<<dp[n-1].S<<"\n";
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);
ld res=1e12;
for(ld l=-1e12,r=1e12,i=0;i<=80;i++){
ld m=(l+r)/2;
// cout<<m<<" "<<check(m)<<"\n";
if(check(m)<=k){
r=m;
res=m;
}
else l=m;
}
// check(-1e8);
// cout<<check(-1e8)<<" "<<check(0)<<" "<<check(res)<<" "<<check(1e8)<<"\n";
check(res);
// cout<<dp[n-1].F<<" "<<dp[n-1].S<<" "<<res<<"\n";
return dp[n-1].F-k*res;
}
