#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
if (a.first != b.first) {
return a.first < b.first;
}
return a.second > b.second;
}
const long long inf = 2e18;
long long div_up(long long a, long long b) {
if (a < 0) {
return a / b;
}
return (a + b - 1) / b;
}
long long take_photos(int n, int m, int k, vector<int> x, vector<int> y) {
for (int i = 0; i < n; i++) {
if (x[i] > y[i]) {
swap(x[i], y[i]);
}
}
vector<pair<int, int>> pairs;
for (int i = 0; i < n; i++) {
pairs.push_back({x[i], y[i]});
}
sort(pairs.begin(), pairs.end(), cmp);
vector<pair<int, int>> new_pairs;
new_pairs.push_back({-1, -1});
int max_y = -1;
for (int i = 0; i < n; i++) {
if (max_y < pairs[i].second) {
max_y = pairs[i].second;
new_pairs.push_back(pairs[i]);
}
}
n = new_pairs.size();
vector<long long> l(n), r(n);
for (int i = 0; i < n; i++) {
l[i] = new_pairs[i].first;
r[i] = new_pairs[i].second + 1;
}
k = min(k, n - 1);
auto ans = [&](int lambda) -> pair<long long, int> {
vector<pair<long long, int>> dp(n, {inf, -1});
dp[0] = {0, 0};
vector<long long> a(n), b(n);
auto count_ab = [&](int i) -> void {
a[i] = dp[i].first + l[i + 1] * l[i + 1] - max(0LL, r[i] - l[i + 1]) * max(0LL, r[i] - l[i + 1]);
b[i] = 2 * l[i + 1];
};
vector<pair<long long, int>> ch;
count_ab(0);
ch.push_back({-1, 0});
int ch_from = 0;
for (int i = 1; i < n; i++) {
while (ch_from + 1 < ch.size() && ch[ch_from + 1].first <= r[i]) {
ch_from++;
}
int from = ch[ch_from].second;
dp[i] = {r[i] * r[i] + a[from] - b[from] * r[i] + lambda, dp[from].second + 1};
if (i + 1 == n) {
break;
}
count_ab(i);
while (!ch.empty()) {
int last = ch.back().second;
long long x = ch.back().first;
if (a[last] - b[last] * x < a[i] - b[i] * x ||
a[last] - b[last] * x == a[i] - b[i] * x && dp[last].second < dp[i].second) {
break;
}
ch.pop_back();
}
int last = ch.back().second;
long long x = div_up(a[i] - a[last], b[i] - b[last]);
if (x == ch.back().first) {
x++;
}
ch.push_back({x, i});
if (ch_from >= ch.size()) {
ch_from = ch.size() - 1;
}
}
return dp.back();
};
int l_bin = -1, r_bin = m * m;
while (r_bin - l_bin > 1) {
int mid = (l_bin + r_bin) / 2;
if (ans(mid).second <= k) {
r_bin = mid;
} else {
l_bin = mid;
}
}
int lambda = r_bin;
pair<long long, int> res = ans(lambda);
return res.first - k * lambda;
}
