#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
const long long inf = 2e18;
///first try without coord compress
array<long long,2> check(vector<int>&mns, long long lam){
int las = -1;
int lasct = 0;
int curr = 0;
array<long long,2>ans = {0,0};
///stores: {cost,k} to be minimized
for(int i = 0;i<mns.size();i++){
curr--;
if(curr<mns[i]){
///either make new or take from las
array<long long,2>temp1 = {inf,inf};
if(las!=-1){
///take from las option to be considered
int dx = mns[i]-max(-1,curr);
temp1[0]=ans[0]+2*dx*(i-las)+max(0,mns[i]+mns[i]+1);
temp1[1]=lasct;
}
array<long long,2>temp2 = {ans[0]+mns[i]+mns[i]+1+lam,ans[1]+1};
ans=min(temp1,temp2);
curr=mns[i];
if(ans==temp2){
las=i;
lasct=ans[1];
}
}
else{
ans[0]+=max(0,curr+curr+1);
}
}
return ans;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<int>mns(m,-1e9);
for(int i = 0;i<n;i++){
int dist = max(r[i]-c[i],c[i]-r[i]);
mns[min(r[i],c[i])]=max(mns[min(r[i],c[i])],dist);
}
long long lo = 0;
long long hi = inf/2;
while(lo<hi){
long long mid = (lo+hi)/2;
array<long long,2> curr = check(mns,mid);
if(curr[1]>k){
lo=mid+1;
}
else{
hi=mid;
}
}
array<long long,2>curr = check(mns,lo);
long long ans = curr[0]-k*lo;
return ans;
return 0;
}
