#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]);
}
while (!a.empty() && a.back().c >= c[i]) {
a.pop_back();
}
a.emplace_back(r[i], c[i]);
}
n = (int) a.size();
i64 const INF = (i64) 1e18;
mx = min(mx, n);
vector<vector<i64>> dp(n + 1, vector<i64>(mx + 1, INF));
dp[0][0] = 0;
auto relax = [&](i64& x, i64 y) {
if (y < x) {
x = y;
}
};
auto sqr = [](i64 x) {
return x * x;
};
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i; ++j) {
for (int k = 1; k <= min(mx, i + 1); ++k) {
auto his_c = a[j].c;
auto my_area = sqr(a[i].r - his_c + 1);
auto inter_area = !j ? 0 : sqr(
max<i64>(0, a[j - 1].r - his_c + 1));
relax(dp[i + 1][k], dp[j][k - 1] + my_area - inter_area);
}
}
}
return *min_element(dp.back().begin(), dp.back().end());
}
//int main() {
// int n = 5;
// int m = 7;
// int k = 2;
// vector<int> r{0, 4, 4, 4, 4};
// vector<int> c{3, 4, 6, 5, 6};
// cout << take_photos(n, m, k, r, c) << '\n';
//}
