#include <bits/stdc++.h>
#include "aliens.h"
template <class T>
using Vec = std::vector<T>;
using ll = long long;
using bigll = long long;
constexpr ll square(const ll x) {
return x * x;
}
struct Line {
ll a, b;
ll get(const ll x) const {
return a * x + b;
}
};
struct CHT {
std::deque<Line> line;
CHT(): line() { }
void add(const Line &l) {
while (line.size() >= 2) {
const auto &m = line[line.size() - 1];
const auto &n = line[line.size() - 2];
if (bigll(m.b - n.b) * bigll(m.a - l.a) < bigll(l.b - m.b) * bigll(n.a - m.a)) {
break;
}
line.pop_back();
}
line.push_back(l);
}
ll get(const ll x) {
while (line.size() >= 2) {
const auto &m = line[0];
const auto &n = line[1];
if (m.get(x) < n.get(x)) {
break;
}
line.pop_front();
}
return line[0].get(x);
}
};
ll take_photos(int n, int m, int k, Vec<int> r, Vec<int> c) {
Vec<std::pair<int, int>> star;
{
for (int i = 0; i < n; ++i) {
if (r[i] > c[i]) {
std::swap(r[i], c[i]);
}
c[i] += 1;
}
Vec<int> order(n);
std::iota(order.begin(), order.end(), (int) 0);
std::sort(order.begin(), order.end(), [&](const int i, const int j) {
if (r[i] == r[j]) return c[i] > c[j];
return r[i] < r[j];
});
int last_c = -1;
for (const int i: order) {
if (last_c < c[i]) {
star.emplace_back(r[i], c[i]);
last_c = c[i];
}
}
}
n = (int) star.size();
// const ll fix_coeff = n + 1;
// const auto compute = [&](const ll penalty) {
// Vec<ll> dp(n + 1);
// CHT cht;
// for (int i = 0; i < n; ++i) {
// const ll a = fix_coeff * (-2 * star[i].first);
// const ll dup = (i == 0 ? 0 : std::max(star[i - 1].second - star[i].first, 0));
// const ll b = dp[i] + fix_coeff * (square(star[i].first) - square(dup));
// cht.add(Line { a, b });
// dp[i + 1] = cht.get(star[i].second) + fix_coeff * (square(star[i].second) + penalty) + 1;
// }
// return std::make_pair(dp[n] / fix_coeff, dp[n] % fix_coeff);
// };
// ll ng = -1, ok = (ll) m * m + 1;
// while (ok - ng > 1) {
// const ll md = (ok + ng) / 2;
// (compute(md).second <= k ? ok : ng) = md;
// }
// const auto [cost, usage] = compute(ok);
// return (cost - ok * usage) + ok * (k - usage);
Vec<ll> dp(n + 1, std::numeric_limits<ll>::max());
dp[0] = 0;
for (int step = 0; step < k; ++step) {
CHT cht;
auto next = dp;
for (int i = 0; i < n; ++i) {
const ll a = -2 * star[i].first;
const ll dup = (i == 0 ? 0 : std::max(star[i - 1].second - star[i].first, 0));
const ll b = dp[i] + (square(star[i].first) - square(dup));
cht.add(Line { a, b });
next[i + 1] = std::min(next[i + 1], cht.get(star[i].second) + square(star[i].second));
}
dp = std::move(next);
}
return dp[n];
}
