#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ld long double
const int maxn = 1e5 + 20;
int l[maxn] , r[maxn] , cnt[maxn] , k , n , par[maxn];
ld a[maxn] , b[maxn] , dp[maxn];
ll t2(int x)
{
return 1LL * x * x;
}
vector<int> hull;
int pt;
ld IS(int i , int j)
{
return (b[i] - b[j]) / (ld)(a[j] - a[i]);
}
void add(int i)
{
a[i] = -2 * l[i + 1];
b[i] = dp[i] + t2(l[i + 1]) - t2(max(0 , r[i] - l[i + 1]));
int sz = hull.size();
while(sz > 1 && IS(hull[sz - 2] , hull[sz - 1]) >= IS(hull[sz - 1] , i))
{
hull.pop_back();
sz--;
}
hull.pb(i);
}
ld f(int ind , int x)
{
return a[ind] * x + b[ind];
}
int get(int x)
{
if(pt >= (int)hull.size())
pt = (int)hull.size() - 1;
while(pt + 1 < (int)hull.size() && f(hull[pt] , x) >= f(hull[pt + 1] , x))
pt++;
return hull[pt];
}
int check(ld x)
{
memset(cnt , 0 , sizeof cnt);
dp[0] = 0;
hull.clear();
for(int i = 1; i <= n; i++)
{
add(i - 1);
int ind = get(r[i]);
par[i] = ind;
dp[i] = f(ind , r[i]) + t2(r[i]) + x;
cnt[i] = cnt[ind] + 1;
}
return cnt[n];
}
long long take_photos(int N, int m, int K, vector<int> R, vector<int> C)
{
m = m;
k = K;
n = N;
vector<pair<int , int> > tmp;
for(int i = 0; i < n; i++)
{
l[i] = min(R[i] , C[i]) , r[i] = max(R[i] , C[i]);
tmp.pb({r[i] , -l[i]});
}
sort(tmp.begin() , tmp.end());
for(int i = 0; i < n; i++)
{
l[i] = -tmp[i].second;
r[i] = tmp[i].first;
}
tmp.clear();
int mn = 1e9;
for(int i = n - 1; i >= 0; i--)
if(mn > l[i])
{
mn = l[i];
tmp.pb({l[i] , r[i]});
}
reverse(tmp.begin() , tmp.end());
n = tmp.size();
for(int i = 1; i <= n; i++)
l[i] = tmp[i - 1].first , r[i] = tmp[i - 1].second + 1;
r[0] = l[0] = -1;
if(k > n)
{
check(0);
return dp[n];
}
ld lx = -1e18 , rx = 1e18;
for(int _ = 0; _ < 200; _++)
{
ld mx = (lx + rx) / 2;
int tmp = check(mx);
if(tmp == k)
{
rx = mx;
break;
}
if(tmp <= k)
rx = mx;
else
lx = mx;
}
check(rx);
ld tmpx = dp[n] - k * rx;
if(fabs(tmpx - ceil(tmpx)) < 0.1)
tmpx = ceil(tmpx);
return (ll)tmpx;
}
