#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#pragma once
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Line {
mutable ll k, m, p;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
map<pair<ll,ll>,int > M;
using ll = long long;
using pli = pair<ll, int>;
using pii = pair<int, int>;
#define F first
#define S second
struct CHT {
struct line {
ll m, c;
int cnt;
line(ll m, ll c, int cnt) : m(m), c(c), cnt(cnt) {}
ll get(ll x) { return m*x + c; }
};
bool bad(line l1, line l2, line l3) {
return (l3.c-l1.c)*(l1.m-l2.m) <= (l2.c-l1.c)*(l1.m-l3.m);
}
vector<line> f;
int idx;
void update(ll m, ll c, int cnt) {
line l(m, c, cnt);
while (f.size() > 1 && bad(f[f.size()-2], f[f.size()-1], l))
f.pop_back();
f.push_back(l);
}
pli query(ll x) {
idx = min(idx, (int)f.size()-1);
while (idx < f.size()-1 && f[idx].get(x) > f[idx+1].get(x))
++idx;
return pli(f[idx].get(x), f[idx].cnt);
}
void clear() {
f.clear();
idx = 0;
}
} cht;
struct LineContainer : multiset<Line, less<>> {
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
static const ll inf = LLONG_MAX;
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b); }
bool isect(iterator x, iterator y) {
if (y == end()) return x->p = inf, 0;
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m) {
auto z = insert({k, m, 0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
ll query(ll x) {
assert(!empty());
auto l = *lower_bound(x);
return l.k * x + l.m;
}
Line getLine(ll x)
{
assert(!empty());
auto l = *lower_bound(x);
return l;
}
};
bool cmp(pair<long long,long long> a,pair<long long,long long> b)
{
if(a.first==b.first)
return a.second>b.second;
return a.first<b.first;
}
bool inters(pair<int,int> a,pair<int,int> b)
{
if(a.first<=b.first && a.second>=b.second)
return true;
return false;
}
pair<ll,ll> pics(long long penalty,int n,int m,vector<int>& r,vector<int>& c)
{
vector<pair<long long,long long> > obj;
vector<pair<long long,long long> > aux;
for(int i = 0;i<n;i++)
aux.emplace_back(1LL*min(r[i],c[i]),1LL*max(r[i],c[i]));
sort(aux.begin(),aux.end(),cmp);
obj.emplace_back(-1,-1);
for(auto it:aux)
{
if(!inters(obj.back(),it))
obj.push_back(it);
}
M.clear();
n = obj.size();
vector<long long> dp;
vector<int> pics;
dp.resize(n+1);
pics.resize(n+1);
// LineContainer lc;
//lc.clear();
cht.clear();
cht.update(-2*obj[1].first,-(-dp[0]-obj[1].first*obj[1].first),0);
// M[make_pair(2*obj[1].first,-dp[0]-obj[1].first*obj[1].first)] = 0;
for(int i=1;i<n;i++)
{
long long zi = obj[i].second+1;
pair<long long,int> best = cht.query(zi);
long long res = best.first;
dp[i] = res + zi * zi + penalty;
pics[i] = 1 + best.second;
if(i==(n-2)) continue;
long long intersection = max(0LL,obj[i].second-obj[i+1].first+1LL)*max(0LL,obj[i].second-obj[i+1].first+1LL);
long long a = 2 * obj[i + 1].first;
long long b = -dp[i] - obj[i + 1].first * obj[i + 1].first + intersection;
cht.update(-a,-b,pics[i]);
//lc.add(-a,-b,pics[i]);
// M[make_pair(a,b)] = pics[i];
}
return make_pair(dp[n-1],pics[n-1]);
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
long long st = 0;
long long dr = 1LL*m*m+10LL;
long long sol;
pair<ll,ll> best;
while(st<dr)
{
long long mid = (st+dr)>>1;
if(pics(mid,n,m,r,c).second<=k)
{
sol=mid;
best = pics(mid,n,m,r,c);
dr = mid;
}
else st = mid+1;
}
return pics(st,n,m,r,c).first - sol * pics(st,n,m,r,c).second;
}
