#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
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]]);
}
}
auto relax = [&](i64& x, i64 y) {
if (y < x) {
x = y;
return true;
}
return false;
};
auto sqr = [](i64 x) {
return x * x;
};
n = (int) a.size();
i64 const INF = (i64) 1e18;
mx = min(mx, n);
vector<i64> dp(n + 1, INF);
dp[0] = 0;
for (int k = 0; k < mx; ++k) {
vector<i64> new_dp(n + 1, INF);
new_dp[0] = 0;
function<void(int, int, int, int)> solve =
[&](int l, int r, int ll, int rr) {
if (l > r) {
return;
}
int m = (l + r) / 2;
int opt = -1;
for (int j = ll; j <= min(m, rr); ++j) {
auto his_c = a[j].c;
auto my_area = sqr(a[m].r - his_c + 1);
auto inter_area = !j ? 0 : sqr(
max<i64>(0, a[j - 1].r - his_c + 1));
if (relax(new_dp[m + 1], dp[j] + my_area - inter_area)) {
opt = j;
}
}
solve(l, m - 1, ll, opt);
solve(m + 1, r, max(opt, 0), rr);
};
solve(0, n - 1, 0, n);
dp.swap(new_dp);
}
return dp.back();
}
//int main() {
// vector<int> r{0, 2, 3};
// vector<int> c{2, 2, 1};
// int n = (int) r.size();
// int m = -1;
// int k = n;
// cout << take_photos(n, m, k, r, c) << '\n';
//}
