#include "aliens.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;
#define cerr if(1) cerr
const Int INF = 1e18;
const Int N = 1e5+5;
// const Int K = 505;
const Int M = 1e6+5;
struct line {
Int m, c;
int idx;
Int eval(Int x) { return m * x + c; }
Int cut(line l) {
return (c - l.c) / (l.m - m);
}
};
struct Cht {
line s[N];
int st = 1, ed = 0;
void upd(line cur) {
while(ed-st+1>=2 && cur.cut(s[ed])<=s[ed].cut(s[ed-1])) --ed;
s[++ed] = cur;
}
line qry(Int x) {
while(ed-st+1>=2 && s[st].eval(x) > s[st+1].eval(x)) st++;
return s[st];
}
};
Int n, m, k;
V<Int> l, r;
Int dp[N], cnt[N];
inline Int sqr(Int x){return x*x;}
void solve(Int cost){
Cht cht;
dp[0] = sqr(r[0]-l[0]+1) +cost;
cnt[0] = 1;
rep(i,1,n){
// dp[i] = sqr(r[i]-l[0]+1) +cost;
// cnt[i] = 1;
// rep(j,1,i+1){
// Int x = dp[j-1] +sqr(r[i]-l[j]+1) -(l[j]<=r[j-1] ? sqr(r[j-1]-l[j]+1):0) + cost;
// if(x < dp[i]){
// dp[i] = x;
// cnt[i] = cnt[j-1]+1;
// }
// if(x==dp[i]){
// cnt[i] = min(cnt[i], cnt[j-1]+1);
// }
// }
Int m = -2*l[i];
Int c = l[i]*l[i]-2*l[i] +dp[i-1] -(l[i]<=r[i-1] ? sqr(r[i-1]-l[i]+1):0);
line cur = {m, c, i};
cht.upd(cur);
Int from0 = sqr(r[i]-l[0]+1) +cost;
Int not0 = r[i]*r[i] +2*r[i] +1 +cht.qry(r[i]).eval(r[i]) +cost;
if(from0 <= not0){
dp[i] = from0;
cnt[i] = 1;
}
else{
dp[i] = not0;
cnt[i] = cnt[cht.qry(r[i]).idx-1] + 1;
// cnt[i] = mpcnt[{bm,bc}] + 1;
}
// dbg(dp[i]);
// dbg(cnt[i]);
}
}
Int take_photos(int _n,int _m,int _k,V<int> _l,V<int> _r){
n = _n; m = _m; k = _k;
l = V<Int>(all(_l));
r = V<Int>(all(_r));
// remove subsegments
V<int> ord;
rep(i,0,n){
if(l[i] > r[i]) swap(l[i], r[i]);
ord.push_back(i);
}
sort(all(ord),[&](int i,int j){
if(l[i]==l[j]) return r[i] < r[j];
return l[i] > l[j];
});
V<int> stak;
for(int i : ord){
while(!stak.empty() && r[stak.back()]<=r[i]) stak.pop_back();
stak.push_back(i);
}
reverse(all(stak));
ord.swap(stak);
// result is ordered from l
// reorder l[] and r[]
{
V<Int> vl, vr;
for(int i : ord){
// cerr << l[i] _ r[i] << nl;
vl.push_back(l[i]);
vr.push_back(r[i]);
}
l.swap(vl);
r.swap(vr);
}
n = ord.size();
// find minimum cost to make <= k merging
Int cost = -1;
for(Int J=1LL<<42; J; J/=2){
// for(Int J=m*m; J; J/=2) rep(loop,0,2){
// {
// check cost+J
solve(cost+J);
if(cnt[n-1] > k) cost+=J;
else ;
}
cost++;
// dbg(k);
solve(cost-1);
Int a = dp[n-1], b = cnt[n-1];
Int ans1 = a - b*(cost-1);
// dbg(cnt[n-1]);
solve(cost);
Int c = dp[n-1], d = cnt[n-1];
Int ans2 = c - d*cost;
// dbg(cnt[n-1]);
if(k>=n) return ans2;
// linear progression from ans1 to ans2
Int ans = ans1 + (k-b)*(ans2-ans1)/(d-b);
// dbg(k);
// dbg(cnt[n-1]);
// assert(cnt[n-1] <= k);
// Int ans = dp[n-1] - cnt[n-1]*cost;
return ans;
}
