#include "aliens.h"
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N = 100005, inf = 1e12;
ll n, m, k;
pll dt[N];
vector<pll> raw, a;
struct hull {
deque<pair<pll, ll> > v;
void clear () {v.clear();}
bool well (pll &A, pll &B, pll &C) {
return (B.Y - A.Y) * (A.X - C.X) < (C.Y - A.Y) * (A.X - B.X);
}
ll val (pll &T, ll P) {return T.X*P+T.Y;}
void upd (pair<pll, ll> A) {
for(ll i=v.size();i-->1;) {
if(well(v[i-1].X, v[i].X, A.X)) break;
else v.pop_back();
}
v.push_back(A);
}
pll get (ll P) {
while(v.size() > 1) {
if(val(v[0].X, P) <= val(v[1].X, P)) break;
else v.pop_front();
}
return pll(val(v[0].X, P), v[0].Y+1);
}
} h;
ll sq (ll X) {return X*X;}
pll solve (ll L) {
h.clear();
h.upd({pll(-2*(a[0].X-1), sq(a[0].X-1) + L), 0});
for(ll i=0;i<n;i++) {
auto T = h.get(a[i].Y);
dt[i] = {T.X + sq(a[i].Y), T.Y};
if(i+1 == n) continue;
h.upd({{-2*(a[i+1].X-1), sq(a[i+1].X-1) - sq(max(0ll, a[i].Y-a[i+1].X+1)) + dt[i].X + L}, T.Y});
}
return dt[n-1];
}
ll take_photos(int _n, int _m, int _k, vector<int> r, vector<int> c) {
m = _m; k = _k;
for(ll i=0;i<_n;i++) {
if(r[i] < c[i]) raw.push_back(pll(r[i], c[i]));
else raw.push_back(pll(c[i], r[i]));
}
sort(raw.begin(), raw.end());
for(auto &T : raw) {
if(a.empty() || a.back().Y < T.Y) a.push_back(T);
}
n = a.size();
ll S = 0, E = inf;
while(S<E) {
ll M = (S+E)/2;
solve(M).Y <= k ? E = M : S = M+1;
}
return solve(S).X - k * S;
}
