#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using real_t = long double;
struct line {
i64 k, b;
[[nodiscard]] i64 apply(i64 x) const {
return k * x + b;
}
};
real_t inter(line const& a, line const& b) {
return static_cast<real_t>(a.b - b.b) / (b.k - a.k);
}
struct hull {
struct item {
line l;
real_t from;
real_t to;
item(line l_, real_t from_, real_t to_) : l(l_), from(from_), to(to_) {}
};
vector<item> lines;
real_t const inf = 1e20;
int ptr = 0;
void add_line(line const& l) {
while ((int) lines.size() >= 2 &&
inter(l, lines.back().l) <=
inter(lines.back().l, lines[lines.size() - 2].l)) {
lines.pop_back();
}
if (lines.empty()) {
lines.emplace_back(l, -inf, inf);
} else {
auto x = inter(l, lines.back().l);
lines.back().to = x;
lines.emplace_back(l, x, inf);
}
}
i64 get(i64 x) {
ptr = min(ptr, (int) lines.size() - 1);
while (x > lines[ptr].to) {
++ptr;
}
return lines[ptr].l.apply(x);
}
};
i64 take_photos(int n, int, int mx, vector<int> r, vector<int> c) {
struct cell {
int r, c;
cell(int r_, int c_) : r(r_), c(c_) {}
};
vector<cell> a;
{
for (int i = 0; i < n; ++i) {
if (r[i] < c[i]) {
swap(r[i], c[i]);
}
}
vector<int> p(n);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int i, int j) {
if (r[i] != r[j]) {
return r[i] < r[j];
}
return c[i] > c[j];
});
for (int i = 0; i < n; ++i) {
while (!a.empty() && a.back().c >= c[p[i]]) {
a.pop_back();
}
a.emplace_back(r[p[i]], c[p[i]]);
}
}
n = (int) a.size();
mx = min(mx, n);
i64 const INF = (i64) 1e18;
vector<vector<i64>> dp(n + 1, vector<i64>(mx + 1, INF));
fill(dp[0].begin(), dp[0].end(), 0);
auto relax = [&](i64& x, i64 y) {
if (y < x) {
x = y;
}
};
auto sqr = [](i64 x) {
return x * x;
};
for (int k = 1; k <= mx; ++k) {
hull cht;
for (int i = 0; i < n; ++i) {
// dp[i + 1][k]
auto ci = !i ? 0 : sqr(
max<i64>(0, a[i - 1].r - a[i].c + 1));
cht.add_line({-2 * a[i].c, sqr(a[i].c) + dp[i][k - 1] - ci});
dp[i + 1][k] = sqr(a[i].r + 1) + cht.get(a[i].r + 1);
}
}
return dp.back().back();
}
//int main() {
// vector<int> r{0, 4, 4, 4, 4};
// vector<int> c{3, 4, 6, 5, 6};
// int n = (int) r.size();
// int m = -1;
// int k = n;
// cout << take_photos(n, m, k, r, c) << '\n';
//}
