#include<bits/stdc++.h>
#include "aliens.h"
#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k)) & 1)
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
const int maxn = 1e5 + 10, mod = 1e9 + 7;
const ll inf = 1e13 + 10, INF = 1e18;
pll dp[maxn];
int mn[maxn];
struct CHT{
vector<pair<pll, ll>> v;
void add(ll a, ll b, ll c){
v.PB({{a, b}, c});
}
pll ask(ll x){
ll ans = INF;
for(auto [p, c] : v){
ans = min(ans, p.F * x + p.S);
}
ll ans2 = INF;
for(auto [p, c] : v){
if(ans == p.F * x + p.S)
ans2 = min(ans2, c);
}
return {ans, ans2};
}
void clear(){
v.clear();
}
};CHT cht;
pll solve(vector<pii> &seg, ll c){
cht.clear();
cht.add(seg[0].F, 1ll * seg[0].F * seg[0].F, 0);
for(int i = 1; i <= sz(seg); i++){
int mn = i == sz(seg) ? (seg[i-1].S + 1) : seg[i].F;
mn = min(mn, seg[i-1].S + 1);
dp[i] = cht.ask(-2 * (seg[i-1].S + 1));
dp[i].F+= -1ll * mn * mn + 2ll * (seg[i-1].S + 1) * mn + c;
dp[i].S++;
if(i < sz(seg))
cht.add(seg[i].F, dp[i].F + 1ll * seg[i].F * seg[i].F, dp[i].S);
// dp[i] = {INF, INF};
//for(int j = 0; j < i; j++)
// dp[i] = min(dp[i], (pll){ dp[j].F - 2ll * (seg[i-1].S + 1) * seg[j].F + 1ll * seg[j].F * seg[j].F - 1ll * mn * mn + 2ll * (seg[i-1].S + 1) * mn + c, dp[j].S + 1 });
// dp[i] = min(dp[i], (pll){ dp[j].F + f(seg[i-1].S - seg[j].F + 1) - f(seg[i-1].S - mn + 1) + c, dp[j].S + 1 });
}
return dp[sz(seg)];
}
ll take_photos(int m, int n, int k, vector<int> X, vector<int> Y){
vector<pii> _seg, seg;
for(int i = 0; i < m; i++){
if(X[i] > Y[i])
swap(X[i], Y[i]);
_seg.PB({X[i], Y[i]});
}
sort(_seg.begin(), _seg.end());
for(pii p : _seg){
if(seg.empty() || seg.back().S < p.S)
seg.PB(p);
}
ll l = -1, r = inf;
while(r-l > 1){
ll mid = (l+r) >> 1;
pll p = solve(seg, mid);
if(p.S > k)
l = mid;
else
r = mid;
}
pll p = solve(seg, r);
return 1ll * p.F - 1ll * k * r;
}
