#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
int n,k;
vector<pair<int,int>> segments;
vector<ll> rem;
int cnt;
pair<ll,ll> calc(ll cst){
vector<pair<ll,ll>> dp = vector<pair<ll,ll>> (cnt,{1e18,1e18});
for(int i=0;i<cnt;i++){
for(int j=i;j>=0;j--){
pair<ll,ll> nxt = (j ? dp[j-1] : make_pair(0ll,0ll));
int fr = segments[j].first;
int to = segments[i].second;
ll add = to - fr + 1;
add *= add;
add -= rem[j];
if(nxt.first <= ll(1e18) - add - cst){
nxt.first += add+cst;
nxt.second++;
dp[i] = min(dp[i] , nxt);
}
}
}
return dp[cnt-1];
}
ll find_answer(){
ll md,lo=1,hi=1e15,lamda = -1;
while(lo <= hi){
md = (lo + hi)/2;
ll used = calc(md).second;
if(used <= k){
hi = md-1;
lamda = md;
}else{
lo = md+1;
}
}
assert(lamda != -1);
pair<ll,ll> ans = calc(lamda);
return ans.first - lamda * k;
}
ll take_photos(int N,int m,int K,vector<int> R, vector<int> C){
n = N;k = K;
vector<pair<int,int>> tmp;
for(int i=0;i<n;i++){
int r = R[i];
int c = C[i];
tmp.push_back({max(r,c) , min(r,c)});
}
sort(tmp.begin(),tmp.end());
set<pair<int,int>> st;
for(int i=0;i<n;i++){
int l = tmp[i].second;
int r = tmp[i].first;
while(st.size() && -st.begin()->first >= l){
st.erase(st.begin());
}
st.insert({-l,r});
}
while(st.size()){
pair<int,int> it = *st.begin();
st.erase(st.begin());
it.first = -it.first;
// cout << it.first << ' ' << it.second << endl;
segments.push_back(it);
}
reverse(segments.begin(),segments.end());
cnt = segments.size();
rem.resize(cnt);
for(int i=1;i<cnt;i++){
int fr = segments[i].first;
int bf = segments[i-1].second;
if(bf >= fr){
rem[i] = bf - fr + 1;
rem[i] *= rem[i];
}
}
ll ans = find_answer();
return ans;
}
