#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = 10e10;
struct line
{
long long c, m;
line(long long _c, long long _m) {c = _c;m=_m;}
long long operator()(long long x)
{
return c+m*x;
}
long long inter(line l)
{
return (c-l.c)/(l.m-m);
}
};
struct CHT
{
deque<line> dq;
deque<long long> pr;
CHT() {dq.push_back(line(0, 0));pr.push_back(0);}
void add(line l, long long k)
{
while (dq.size() > 2 && dq[dq.size()-2].inter(l) >= dq.back().inter(l))
{
dq.pop_back();
pr.pop_back();
}
dq.push_back(l);
pr.push_back(k);
}
pair<int, int> get_best(long long x)
{
while (dq.size() > 1 && dq[1](x) >= dq[0](x))
{
dq.pop_front();
pr.pop_front();
}
return {dq[0](x), pr[0]};
}
};
long long sq(long long x)
{
return x*x;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
// get rid of useless points
vector<pair<long long, long long>> pnts;
for (long long i = 0; i < n; i++)
{
if (r[i] < c[i]) swap(r[i], c[i]);
pnts.push_back({r[i], c[i]});
}
sort((pnts).begin(), pnts.end(), [](pair<int, int> pr, pair<int, int> dr){
if (pr.first != dr.first) return pr < dr;
return pr > dr;
});
vector<pair<long long, long long>> a;
a.push_back(pnts[0]);
for (long long i = 1; i < n; i++)
if (a.back().second < pnts[i].second)
a.push_back(pnts[i]);
// cout << a.size() << "\n";
// for (auto v:a)
// cout << v.first << " :: " << v.second << "\n";
// lambda optimization, v a so vse pomembne tocke
long long l = 0, d = inf, lambda = 0;
CHT ch;
vector<pair<long long, long long>> dp;
while (l <= d)
{
long long lamb = (l+d)/2;
ch = CHT();
dp = vector<pair<long long, long long>>(a.size());
for (long long i = 0; i < a.size(); i++)
{
auto [r, c] = a[i];
// if (lamb == 0)
// cout << "-> t: " << sq(r-a[0].second+1)+lamb << " " << r << " " << c << "\n";
dp[i].first = sq(r-a[0].second+1)+lamb;
// if (lamb == 0)
// cout << "---> " << dp.back().first << "\n";
dp[i].second = 1;
if (i)
{
auto [zc, tk] = ch.get_best(r);
long long t = zc+r*r+lamb;
dp[i] = min(dp[i], {t, tk+1});
}
ch.add(line(-2*(c-1), dp[i].first+sq(c-1)+sq(max(0ll, r-c+1))), dp[i].second);
}
// if (lamb == 0)
// cout << "-> " << dp.back().first << "\n";
// cout << lamb << " " << dp.back().first << " " << dp.back().second << "\n";
if (dp.back().second <= k)
d = lamb-1;
else
l = lamb+1;
lambda = lamb;
}
return dp.back().first-dp.back().second*lambda;
}
