#include "bits/stdc++.h"
#define ll long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll)a.size()
using namespace std;
const ll N = (ll) 1e5 + 5;
const ll INF = (ll) 1e18 + 5;
const ll INF2 = (ll) 1e12 + 5;
vector<array<ll,2>> v;
struct Line{
ll sl,cn,tag;
inline void Set_Line(ll _a,ll _b, ll _tag){sl = _a, cn = _b, tag = _tag;}
inline ll get_val(ll _x){return _x * sl + cn;}
};
struct LiChao{
vector<Line> seg;
LiChao(ll _m){
seg.resize(4 * _m + 5);
for(int i = 0 ; i < 4 * _m + 5 ; i++) seg[i].Set_Line(0, INF, 0);
}
void add(ll rt, ll l, ll r, Line u){
ll mid = (l + r) / 2;
if(u.get_val(mid) < seg[rt].get_val(mid)) swap(seg[rt], u);
if(l == r) return;
if(u.sl >= seg[rt].sl) add(rt * 2, l, mid, u);
else add(rt * 2 + 1, mid + 1, r, u);
}
Line get_min(ll rt, ll l, ll r, ll ind){
if(l == r) return seg[rt];
Line res = seg[rt] , curi;
ll mid = (l + r) / 2;
if(ind <= mid) curi = get_min(rt * 2, l, mid, ind);
else curi = get_min(rt * 2 + 1, mid + 1, r, ind);
if(curi.get_val(ind) < res.get_val(ind)) swap(curi,res);
return res;
}
};
array<ll,2> wqs_binary_search(ll lambda){
ll n = sz(v) - 1;
vector<ll> dp(n+5,INF),Use(n+5,INF);
Use[0] = dp[0] = 0;
LiChao T(N);
Line ekle;
ekle.Set_Line(-2 * v[1][0], lambda + v[1][0] * v[1][0], 0);
T.add(1,1,N,ekle);
for(int i = 1; i <= n ; i++){
ll a = v[i][0] , b = v[i][1] + 1;
Line Gel = T.get_min(1, 1, N, b);
dp[i] = Gel.get_val(b) + b * b;
Use[i] = Gel.tag + 1;
if(i < n){
Line ekle2;
ekle2.Set_Line(-2 * v[i + 1][0], lambda + dp[i] + v[i + 1][0] * v[i + 1][0]
- max(0LL,b - v[i + 1][0]) * max(0LL,b - v[i + 1][0]), Use[i]);
T.add(1,1,N,ekle2);
}
}
return {dp[n],Use[n]};
}
ll take_photos(int _n,int _m,int _k,vector<int> r,vector<int> c){
ll n = _n, m = _m, k = _k;
for(ll i=0;i<n;i++){
ll a = r[i], b = c[i];
if(a > b) swap(a, b);
v.push_back({a,b});
}
sort(all(v));
vector<array<ll,2>> xdd;
xdd.push_back({-1LL, -1LL});
for(ll i = 0; i < n; i++){
if(v[i][0] == xdd.back()[0]){
xdd.pop_back();
xdd.push_back(v[i]);
}
else if(xdd.back()[1] < v[i][1]) xdd.push_back(v[i]);
}
swap(v,xdd);
ll res_l = 0, res_r = INF2;
while(res_l < res_r){
ll lol = (res_l+res_r)/2;
array<ll,2> hmm = wqs_binary_search(lol);
if(hmm[1] > k) res_l = lol + 1;
else res_r = lol;
}
array<ll,2> ANS = wqs_binary_search(res_l);
return ANS[0] - res_l * ANS[1];
}
/*void _(){
int n,m,k;
cin >> n >> m >> k;
for(int i = 0; i < n; i++){
int a,b;
cin >> a >> b;
if(a>b) swap(a,b);
v.push_back({a,b});
}
sort(all(v));
vector<array<ll,2>> xdd;
xdd.push_back({-1LL, -1LL});
for(int i=0;i<n;i++){
if(v[i][0] == xdd.back()[0]){
xdd.pop_back();
xdd.push_back(v[i]);
}
else if(xdd.back()[1] < v[i][1]) xdd.push_back(v[i]);
}
swap(v,xdd);
ll res_l = -INF2, res_r = INF2;
while(res_l < res_r){
ll lol = (res_l+res_r)/2;
array<ll,2> hmm = wqs_binary_search(lol);
if(hmm[1] > k) res_l = lol + 1;
else res_r = lol;
}
array<ll,2> ANS = wqs_binary_search(res_l);
cout << ANS[0] - res_l * ANS[1] << '\n';
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/
