#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;
struct con{
int l,used;
ll prev;
con(int left,int uu,ll pp){
l = left;used = uu;prev = pp;
}
pair<ld,int> getcost(ld x){
ld d = l-x;
return {d*d + prev ,used};
}
ld tover(con rhs){
ld l1 = l,l2 = rhs.l;
ld c = prev - rhs.prev;
ld all = l1*l1 - l2 * l2 + c;
ld rem = 2 * l1 - 2 * l2;
all /= rem;
return all;
}
};
pair<ll,ll> calc(ll cst){
pair<ll,int> curbest = {0,0};
int fptr=0,bptr=0;
vector<con> bag(cnt+2,con(0,0,0));
for(int i=0;i<cnt;i++){
int l = segments[i].first;
int r = segments[i].second;
con nxt = con(l-1,curbest.second+1,curbest.first + cst-rem[i]);
while(bptr - fptr >= 2 && bag[bptr-2].tover(bag[bptr-1]) >= bag[bptr-2].tover(nxt))bptr--;
bag[bptr++] = nxt;
while(fptr + 1 < bptr && bag[fptr].getcost(r) >= bag[fptr+1].getcost(r))fptr++;
curbest = bag[fptr].getcost(r);
}
return curbest;
}
ll find_answer(){
ll md,lo=0,hi=1e11,lamda = -1;
pair<ll,ll> tst = calc(0);
if(tst.second <= k)return tst.first;
while(lo <= hi){
md = (lo + hi)/2;
ll used = calc(md).second;
if(used <= k){
hi = md-1;
lamda = md;
}else{
lo = md+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;
}
