#include <bits/stdc++.h>
#include "aliens.h"
#define DIMN 100010
#define DIMM 1000010
#define INF 2000000000000000000LL
using namespace std;
int n,k,m,i,j,x,y;
vector <int> r,c;
long long dp[DIMN],cnt[DIMN];
pair <int, int> v[DIMN];
struct dreapta{
long long a,b,cnt;
};
struct cmp{
bool operator()(dreapta x, dreapta y){
if (x.a == y.a)
return x.b < y.b;
return x.a > y.a; /// descrescator dupa panta
}
};
set <dreapta,cmp> s;
long long f (long long a, long long b, int x){
if (a == INF && b == INF)
return INF;
return a*x + b;
}
bool intersectie (pair<long long,long long> c, pair<long long,long long> b, pair<long long,long long> a){
return (a.second-c.second)*(b.first-a.first) < (a.second-b.second)*(c.first-a.first);
}
void add (long long a, long long b, long long cnt){
set <dreapta> ::iterator it = s.find({a,b,cnt});
if (it != s.end() && it->a == a && it->b == b) /// nu are sens sa mai adaug dreapta
return;
/// in set le am sortate dupa panta
/// acum trebuie sa vad ce drepte scoate si din stanga si din dreapta
it = s.lower_bound({a,b,cnt});
if (it != s.begin()){
it--; /// primul mai mic
int ok = 1;
do{
if (it != s.begin()){ /// mai am drepte in stanga
set <dreapta> :: iterator it2 = it;
it2--;
if (intersectie(make_pair(a,b),make_pair(it->a,it->b),make_pair(it2->a,it2->b))){
s.erase(it);
it = it2;
} else ok = 0; /// nu mai scoate nimic
} else ok = 0; /// nu mai am drepte
} while (ok);
}
it = s.lower_bound({a,b,cnt});
if (it != s.begin() && it != s.end()){
set <dreapta> :: iterator it2 = it;
it2--;
if (intersectie (make_pair(it->a,it->b),make_pair(a,b),make_pair(it2->a,it2->b)) == 0){
s.insert({a,b,cnt});
return;
}}
else s.insert({a,b,cnt});
}
pair<long long, long long> query (long long x){
/// daca am query uri crescatoare pot sa sterg din fata
set <dreapta> :: iterator it = s.begin();
while (it != s.end()){
set <dreapta> :: iterator it2 = it;
it2++;
if (it2 == s.end())
break;
if (it->a*x+it->b > it2->a*x+it2->b){
/// il sterg pe it
s.erase(it);
it = it2;
} else break;
}
return make_pair(it->a * x + it->b,it->cnt);
}
long long patrat (long long x){
return x*x;
}
long long modul (long long x){
return max (x,-x);
}
inline int cmp (pair<int,int> a, pair<int,int> b){
if (a.first == b.first)
return a.second > b.second;
return a.first < b.first;
}
void solve (long long lambda){
/// dp[i] - costul mimim daca am primele i puncte
/// cnt[i] - de cate subsecvente am nevoie
//for (int i=0;i<=n;++i)
// dp[i] = cnt[i] = 0;
//for (int i=1;i<=4*m;++i)
// aint[i] = {INF,INF,0};
s.clear();
for (int i=1;i<=n;++i){
add (-2*v[i].first,dp[i-1] + patrat(v[i].first) - patrat(max(0,v[i-1].second - v[i].first + 1)), cnt[i-1]);
pair <long long, long long> sol = query (v[i].second+1);
dp[i] = sol.first + patrat (v[i].second+1) + lambda;
cnt[i] = sol.second + 1;
}
}
long long take_photos (int N, int M, int K, std::vector <int> r, std::vector <int> c){
n = N, m = M, k = K;
for (i=0;i<n;++i)
v[i+1] = make_pair(min(r[i],c[i])+1,max(r[i],c[i])+1);
sort (v+1,v+n+1,cmp);
/// elimin intervalele care sunt incluse in altele
int St = -1, Dr = -1, el = 0;
for (i=1;i<=n;++i){
if (!(v[i].first >= St && v[i].second <= Dr)){
v[++el] = v[i];
St = v[i].first, Dr = v[i].second;
}}
n = el;
k = min (k,n);
long long st = 0, dr = INF;
while (st <= dr){
long long lambda = (st + dr)>>1;
solve (lambda);
if (cnt[n] > k)
st = lambda + 1;
else dr = lambda - 1;
}
solve (st);
return dp[n] - k * st;
}
