#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb push_back
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define irep(i,a,b) for(int i = a; i >= b; i--)
typedef long long ll;
typedef long double ld;
//typedef __int128 int128;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<ll,ll> pl;
const int max_n = 1e5+7;
const ll INF = 1e12+7;
struct seg{
ll beg;
ll end;
ll a;
ll b;
ll k;
};
pl arr[max_n];
ll odj[max_n]; //stale!
ll dp[max_n];
ll val_k[max_n];
vector<pl> points; //do pierwszego sortu!
vector<seg> vec;
void calc_ans(ll n, ll eps){
//cout << "\n\ncalc ans od eps: " << eps << '\n';
for(ll i = 1; i <= n; i++){
//dodanie naszego el!
ll a = -2*(arr[i].st-1); ll b = (arr[i].st-1)*(arr[i].st-1)+dp[i-1]-odj[i];
//cout << "\ni: " << i << " a: " << a << " b: " << b << '\n';
//cout << "arr: " << arr[i].st << ' ' << arr[i].nd << '\n';
while(1){
if(vec.empty()){
vec.pb({-INF,INF,a,b,0});
break;
}
ll up = vec.back().b-b; ll down = a-vec.back().a;
ll x = up/down; if(up%down != 0) x++; //jesli to zmieni to xD
//cout << "x: " << x << '\n';
if(x <= vec.back().beg){
vec.pop_back();
continue;
}
//dodajemy nasz
vec[vec.size()-1].end = x-1;
vec.pb({x,INF,a,b,val_k[i-1]});
break;
}
//teraz szukamy najlepszego punktu
ll l = 0; ll r = vec.size()-1; ll ind = 0;
while(l <= r){
ll s = (l+r+1)/2;
//cout << "s: " << s << " beg: " << vec[s].beg << " end: " << vec[s].end << '\n';
if(vec[s].beg <= arr[i].nd && vec[s].end >= arr[i].nd){
ind = s;
break;
}
else if(vec[s].end < arr[i].nd) l = s+1;
else r = s-1;
}
//mamy ind!!!
val_k[i] = vec[ind].k+1;
dp[i] = arr[i].nd*arr[i].nd+eps+vec[ind].a*arr[i].nd+vec[ind].b;
//cout << "ind: " << ind << " ind_a: " << vec[ind].a << " ind_b: " << vec[ind].b << '\n';
//cout << "dp: " << dp[i] << " k: " << val_k[i] << '\n';
}
vec.clear(); //to wazne
}
ll take_photos(int n, int m, int k, vi row, vi col){
//ustawic nowe n!
rep(i,0,n-1){
if(col[i] < row[i]){
//przestawienie na gorna polowe!
int diff = row[i]-col[i];
col[i] += diff;
row[i] -= diff;
}
//cout << "i: " << i << " point: " << row[i] << ' ' << col[i] << '\n';
points.pb({row[i],col[i]});
}
sort(points.begin(),points.end());
int akt_ind = 0;
ll max_c = -1;
rep(i,0,n-1){
if(points[i].nd <= max_c) continue; //jest dalej mniejsze h!
if(i != n-1 && points[i+1].st == points[i].st) continue; //ten sam rząd
arr[++akt_ind] = points[i];
max_c = points[i].nd;
}
//policzyc odj!
rep(i,2,akt_ind){
if(arr[i].st > arr[i-1].nd) continue;
ll val = arr[i-1].nd-arr[i].st+1;
odj[i] = val*val;
}
rep(i,1,akt_ind){
//cout << "i: " << i << " arr: " << arr[i].st << ' ' << arr[i].nd << " odj: " << odj[i] << '\n';
}
k = min(k,akt_ind); //wazne, zeby za duzo prostokatow nie robic!!!
ll l = 0; ll r = INF; ll ans = 0;
while(l <= r){
ll s = (l+r+1)/2;
calc_ans(akt_ind,s);
if(val_k[akt_ind] >= k){
ans = dp[akt_ind]-k*s;
l = s+1;
}
else r = s-1; //zwiekszam kare
}
////cout << "ans: " << ans << '\n';
return ans;
}
