#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cout << a << ' ', abc(b...);
}
#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif
#define ll long long
struct line {
ll m, c; int id;
ll eval(ll x) {
return m * x + c;
}
long double intersectX(line o) const {
return (long double) (c - o.c) / (o.m - m);
}
};
vector<pair<ll, ll>> points;
vector <line> cht ;
int cp;
void add ( line l) {
auto n = cht.size();
while (n >= 2 &&
cht[n-1].intersectX(cht[n -2]) >= l.intersectX(cht[n-1])) {
cht.pop_back();
n = cht.size () ;
}
cht.push_back (l);
cp = min (cp ,(int)cht.size() -1) ;
}
long long query ( long long x) {
while (cp +1 != cht.size() &&
cht [cp].intersectX(cht[cp +1]) < x) cp++;
return cht [cp ].m*x + cht [cp].c;
}
pair<ll, ll> ct(ll c) {
cht.clear();
add({-2 * points[0].first, points[0].first * points[0].first - 2 * points[0].first, 0});
int n= points.size();
vector<ll> dp(n + 5);
ll total = 0;
for (int i = 0; i < n; i++) {
// while (dq.size() >= 2 && dq[0].eval(points[i].second) >= dq[1].eval(points[i].second)) dq.pop_front();
ll cur = query(points[i].second) + (points[i].second + 1) * (points[i].second + 1) + c;
dp[i] = cur;
total = cht[cp].id + 1;
if (i == n-1) break;
line l = {-2 * points[i+1].first, points[i + 1].first * points[i + 1].first - 2 * points[i + 1].first + dp[i] - max(points[i].second - points[i + 1].first + 1, 0LL) * max(points[i].second - points[i + 1].first + 1, 0LL), total};
// while (dq.size() >= 2 && l.intersectX(dq.back()) <= dq.back().intersectX(dq[dq.size() - 2])) dq.pop_back();
// dq.push_back(l);
add(l);
}
return {total, dp[n-1]};
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
for (int i = 0; i < n; i++) {
if (r[i] > c[i]) swap(r[i], c[i]);
points.emplace_back(r[i], c[i]);
}
sort(points.begin(), points.end(), [](pair<int, int> a, pair<int, int> b) {
if (a.second == b.second) {
return a.first > b.first;
} else return a.second < b.second;
});
vector<pair<ll, ll>> final;
for (int i = 0; i < n; i++) {
while (!final.empty() && final.back().first >= points[i].first) final.pop_back();
final.push_back(points[i]);
}
points = final;
test(points);
ll left = 0, right = (ll) m * m;
k = min(k, (int) points.size());
while (left != right) {
ll mid = (left + right) / 2;
auto cur = ct(mid);
if (cur.first > k) left = mid + 1;
else right = mid;
}
auto ans = ct(left);
return ans.second - left * k;
}
