#include "aliens.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
const int N = (int)1e5 + 123, inf = 1e9;
const ll INF = 1e18;
using namespace std;
struct line{
ll k, b;
double X;
int cnt;
double intersect(line a){
return -1.0 * (a.b - b) / (a.k - k);
}
};
struct cvh{
vector< line > v;
int ptr = 0;
void add(line x){
while(v.size() > 1){
line a = v[v.size() - 1];
line b = v[v.size() - 2];
if(x.intersect(a) < x.intersect(b))
v.pop_back();
else
break;
}
if(v.empty()){
x.X = -INF;
}else{
line a = v.back();
x.X = x.intersect(a);
}
v.pb(x);
}
pair<ll, ll> get(ll x, ll add){
if(v.empty())
return {INF, 1};
ptr = min(ptr, (int)v.size());
while(ptr < v.size() && v[ptr].X < x)
ptr++;
pair< ll, ll> res;
res.f = v[ptr - 1].k * x + v[ptr - 1].b;
res.s = v[ptr - 1].cnt + 1;
res.f += add;
return res;
}
};
ll sqr(ll x){
return x * x;
}
pair<ll ,ll> get(ll C, vector< pair<int, int> > &arr){
int n = arr.size();
vector< pair<ll, ll> > dp(n);
vector< line > ln(n, {0, INF});
cvh btr;
for(int i = 0; i < n; i++){
dp[i] = min( mp(sqr(arr[i].s - arr[0].f + 1), 1ll) , btr.get(arr[i].s, sqr(arr[i].s)) );
dp[i].f += C;
if(i != n - 1){
ll b = dp[i].f + sqr(arr[i + 1].f - 1) - sqr(max(0, arr[i].s - arr[i + 1].f + 1));
ll k = - 2 * (arr[i + 1].f - 1);
ln[i].k = k;
ln[i].b = b;
ln[i].cnt = dp[i].s;
}
btr.add(ln[i]);
}
return dp[n - 1];
}
ll take_photos(int n, int m, int k, vector<int> row, vector<int> col) {
vector< pii > arr, tmp;
for(int i = 0; i < n; i++){
int l, r;
l = row[i];
r = col[i];
if(l > r)
swap(l, r);
tmp.pb({l, -r});
}
sort(tmp.begin(), tmp.end());
for(int i = 0, mx = -1; i < n; i++){
int l = tmp[i].f;
int r = -tmp[i].s;
if(r <= mx)
continue;
mx = r;
arr.pb({l, r});
}
n = arr.size();
ll l = 0, r = 1e15;
while(l <= r){
ll m = (l + r) / 2;
if(get(m, arr).s > k)
l = m + 1;
else
r = m - 1;
}
return get(l, arr).f - get(l, arr).s * l;
}
