#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;
} aint[DIMM*4];
long long f (long long a, long long b, int x){
if (a == INF && b == INF)
return INF;
return a*x + b;
}
void add (int nod, int st, int dr, long long a, long long b, long long cnt){
if (st == dr){
if (f(a,b,st) < f(aint[nod].a,aint[nod].b,st))
aint[nod] = {a,b,cnt};
return;
}
int mid = (st+dr)>>1;
int ok_mid = 0, ok_dr = 0;
if (f(a,b,mid) <= f(aint[nod].a,aint[nod].b,mid))
ok_mid = 1;
if (f(a,b,dr) <= f(aint[nod].a,aint[nod].b,dr))
ok_dr = 1;
if (!ok_mid && !ok_dr)
add (nod<<1,st,mid,a,b,cnt);
else {
if (!ok_mid && ok_dr)
add ((nod<<1)|1,mid+1,dr,a,b,cnt);
else {
swap (aint[nod].a,a);
swap (aint[nod].b,b);
swap (aint[nod].cnt,cnt);
if (ok_dr)
add (nod<<1,st,mid,a,b,cnt);
else add ((nod<<1)|1,mid+1,dr,a,b,cnt);
}}}
pair<long long,long long> query (int nod, int st, int dr, int x){
if (st == dr)
return make_pair(f(aint[nod].a,aint[nod].b,x),aint[nod].cnt);
int mid = (st+dr)>>1;
pair<long long,long long> sol = make_pair(INF,0);
if (x <= mid)
sol = query (nod<<1,st,mid,x);
else sol = query ((nod<<1)|1,mid+1,dr,x);
if (sol.first < f(aint[nod].a,aint[nod].b,x))
return sol;
else {
if (sol.first == f(aint[nod].a,aint[nod].b,x) && aint[nod].cnt > sol.second)
return sol;
else return make_pair(f(aint[nod].a,aint[nod].b,x),aint[nod].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<2*m;i++)
aint[i] = {INF,INF,0};
for (int i=1;i<=n;i++){
add (1,1,m,-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 (1,1,m,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]),max(r[i],c[i]));
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;
long long st = 1, 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;
}
