#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
const long long inf = 2e18;
long long inter(array<long long,3>a, array<long long,3> b){
return (a[1]-b[1])/(b[0]-a[0]);
}
pair<long long, int> check(vector<array<int,2>> &rangs, long long lam){
pair<long long,int>dp = {0,0};
vector<array<long long,3>>cht;
///stores: {m,c,num} (num not used for sorting it just there for reasons)
cht.push_back({0,0,0});
int chtind = 0;
for(int i = 0;i<rangs.size();i++){
int l = rangs[i][0];
int r = rangs[i][1];
while(chtind<cht.size()-1&&r>inter(cht[chtind],cht[chtind+1])){
chtind++;
}
if(i){
dp={cht[chtind][0]*r+cht[chtind][1]+r*r+2*r+1+lam,cht[chtind][2]+1};
}
else{
dp={(r-l+1)*(r-l+1)+lam,1};
}
if(i<rangs.size()-1){
array<long long,3>curr = {-2*rangs[i+1][0],dp.first+rangs[i+1][0]*rangs[i+1][0]-2*rangs[i+1][0]-max(0,r-rangs[i+1][0]+1)*max(0,r-rangs[i+1][0]+1),dp.second};
while(cht.size()>1&&inter(cht[cht.size()-1],cht[cht.size()-2])>=inter(cht.back(),curr)){
cht.pop_back();
}
cht.push_back(curr);
chtind=min(chtind,(int)cht.size()-1);
}
}
return dp;
}
vector<array<int,2>>pre(vector<array<int,2>> &arr){
vector<array<int,2>>ans;
sort(arr.begin(),arr.end());
ans.push_back(arr[0]);
for(int i = 1;i<arr.size();i++){
if(arr[i][0]==ans.back()[0]){
ans.back()[1]=arr[i][1];
}
else{
if(arr[i][1]>ans.back()[1]){
ans.push_back(arr[i]);
}
}
}
return ans;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<array<int,2>> rangs(n);
for(int i = 0;i<n;i++){
rangs[i]={min(r[i],c[i]),max(r[i],c[i])};
}
rangs = pre(rangs);
n=rangs.size();
k=min(k,n);
long long lo = 0;
long long hi = 2e12;
while(lo<hi){
long long mid = (lo+hi)/2;
pair<long long,int> p = check(rangs,mid);
if(p.second>k){
lo=mid+1;
}
else{
hi=mid;
}
}
lo--;
pair<long long,int> p = check(rangs,lo);
return p.first-k*lo;
}
