#include "aliens.h"
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
const ll N = 100005, inf = 1e12;
/*
//kactl CHT template
struct Line {
mutable ll k, m, p;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
static const ll inf = LLONG_MAX;
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b); }
bool isect(iterator x, iterator y) {
if (y == end()) return x->p = inf, 0;
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m) {
auto z = insert({k, m, 0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
ll query(ll x) {
assert(!empty());
auto l = *lower_bound(x);
return l.k * x + l.m;
}
};
*/
ll n, m, k;
pair<ll,ll> dt[N];
vector<pair<ll,ll>> mainl, a;
//note class has stuff private by default, struct has public
//just use struct
struct hull{
deque<pair<pair<ll,ll>, ll>> v;
void clear() {v.clear();}
bool aok(pair<ll,ll> &A, pair<ll,ll> &B, pair<ll,ll> &C){
return (B.Y - A.Y) * (A.first - C.first) < (C.Y - A.Y) * (A.first - B.first);
}
ll val(pair<ll,ll> &T, ll P) {return T.first*P+T.Y;}
void upd (pair<pair<ll,ll>, ll> A){
for(ll i=v.size();i-->1;) {
if(aok(v[i-1].first, v[i].first, A.first)) break;
else v.pop_back();
}
v.push_back(A);
}
pair<ll,ll> get(ll P){
while(v.size() > 1) {
if(val(v[0].first, P) <= val(v[1].first, P)) break;
else v.pop_front();
}
return pair<ll,ll>(val(v[0].first, P), v[0].second+1);
}
} h;
ll sq(ll first) {return (ll)((ll)first*(ll)first);}
pair<ll,ll> solve(ll L){
h.clear();
h.upd({pair<ll,ll>(-2*(a[0].first-1), sq(a[0].first-1) + L), 0});
for(ll i = 0; i<n; i++){
auto T = h.get(a[i].second);
dt[i] = {T.first + sq(a[i].second), T.second};
if(i == n) continue;
h.upd({{-2*(a[i+1].first-1), sq(a[i+1].first-1) - sq(max(0ll, a[i].second-a[i+1].first+1)) + dt[i].first + L}, T.second});
}
return dt[n-1];
}
ll take_photos(int nn, int mm, int kk, vector<int> r, vector<int> c) {
m = mm; k = kk;
for(ll i = 0 ; i<nn; i++) {
if(r[i] < c[i]) mainl.push_back(pair<ll,ll>(r[i], c[i]));
else mainl.push_back(pair<ll,ll>(c[i], r[i]));
}
sort(mainl.begin(), mainl.end());
for(auto &T : mainl) {
if(a.empty() or a.back().second < T.second) a.push_back(T);
}
n = a.size();
ll S = 0, E = inf;
while(S < E) {
ll M = (S+E)/2;
solve(M).second <= k ? E = M : S = M+1;
}
return solve(S).first - k * S;
}
/*
ll sq(ll first) {return (ll)((ll)first*(ll)first);}
ll val(pair<ll,ll> &aa, ll bb) {return aa.first*bb+aa.second;}
pair<ll,ll> solve (ll L) {
deque<pair<pair<ll,ll>, ll>> v;
v.clear();
pair<pair<ll,ll>,ll> to_upd = {{-2*(a[0].first-1), sq(a[0].first-1) + L}, 0};
//upd
v.push_back(to_upd);
for(ll i = 0; i < n; i++) {
while(v.size() > 1){
if(val(v[0].first, a[i].second) <= val(v[1].first, a[i].second)) break;
else v.pop_front();
}
pair<ll,ll> getit = {val(v[0].first, P), v[0].second+1};
vpp[i] = {T.first + sq(a[i].second), T.second};
//
}
return vpp[n-1];
}
*/
