// 100 points
#include "aliens.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const ll inf = 1e5+9,K = 509,MX = 1e18+9;
ll n ,k;
pair<ll,ll> dp[inf];
ll sqr(ll x){
return x*x;
}
pair<ll,ll> a[inf];
vector<pair<ll,ll> > all;
bool cmp(pair<ll,ll>x,pair<ll,ll>y ){
if(x.first == y.first)
return x.second > y.second;
return x.first<y.first;
}
struct line {
ll m, c,idx;
ll eval(ll x) { return m * x + c; }
#define ld long double
ld intersectX(line l) {
assert(l.m != m);
return (ld) (c - l.c) / (l.m - m);
}
};
struct LineContainer{
//for maximum
// m increasing and x increasing
//to get m is decreasing x is decreasing -m , -x
deque<line> dq;
#define last dq.size()-1
void add(ll m,ll p,ll idx){
line cur = {m,p,idx};
while (dq.size() >= 2 && dq[last-1].intersectX(cur) <= dq[last-1].intersectX(dq[last]))
dq.pop_back();
dq.push_back(cur);
}
pair<ll,ll> query(ll x){
while (dq.size() >= 2 && dq[0].eval(x) <= dq[1].eval(x))
dq.pop_front();
return make_pair(dq[0].eval(x),dq[0].idx);
}
};
ll solve(ll cost){
memset(dp,61,sizeof(dp));
dp[0] = make_pair(0ll,0ll);
LineContainer lc;
for(ll i=1; i<=n; i++){
ll m = -2ll * a[i].first,
p = sqr(a[i].first) + dp[i-1].first - sqr(max(0ll,a[i-1].second - a[i].first+1) ) - 2ll*a[i].first ;
lc.add(-m,-p,i);
ll add = sqr(a[i].second) + 2ll*a[i].second + 1, x = a[i].second;
dp[i] = lc.query(x);
dp[i].first = add - dp[i].first + cost;
}
int cur = n,cnt = 0;
while(cur)
cnt ++ , cur = dp[cur].second - 1;
return cnt;
}
ll take_photos(int N, int m, int K, vector<int> R, vector<int> c) {
n = N;
k = K;
for(ll i=0;i<n;i++)
R[i] ++,c[i]++,
all.push_back( make_pair(min(R[i],c[i]),max(R[i],c[i]) ) );
sort(all.begin(),all.end(),cmp);
n = 1;
a[1] = all[0];
for(auto o:all){
if(o.second <= a[n].second)
continue;
a[++n] = make_pair(o.first,o.second);
}
k = min(k,n);
ll l = 1 , r = 1e18+9,mid;
while(l<=r){
ll mid = (l+r)/2ll;
if(solve(mid)<=k)
r = mid-1;
else
l= mid +1;
}
solve(r);
return dp[n].first-k*r;
while(r-l > 1){
mid = (l+r)/2ll;
if(solve(mid) <= k)
r = mid;
else
l = mid;
}
solve(r);
return dp[n].first - k*r;
}
