#include <bits/stdc++.h>
long long take_photos1(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
std::vector<std::vector<bool>> used(m, std::vector<bool>(m, false));
for (int i = 0; i < n; ++i) {
int left = r[i], right = c[i];
if (left > right)
std::swap(left, right);
for (int x = left; x <= right; ++x) {
for (int y = left; y <= right; ++y) {
used[x][y] = true;
}
}
}
long long result = 0;
for (int x = 0; x != m; ++x) {
for (int y = 0; y != m; ++y) {
result += used[x][y];
}
}
return result;
}
long long INF = 2e9;
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
if (n == k) {
return take_photos1(n, m, k, r, c);
}
std::vector<std::vector<long long>> dp(n + 1, std::vector<long long>(k + 1, INF));
std::vector<std::pair<int, int>> points(n);
auto cost = [&](int i, int j) {
int r = points[j].first;
int l = points[i].first;
return (r - l + 1) * 1ll * (r - l + 1);
};
auto comparator = [&](const std::pair<int, int>& a, const std::pair<int, int>& b) {
return a.first < b.first;
};
std::sort(points.begin(), points.end(), comparator);
for (int i = 0; i <= k; ++i) {
dp[0][i] = 0;
}
for (int i = 1; i <= n; ++i) {
points[i - 1] = {r[i - 1], c[i - 1]};
for (int t = 0; t < i; ++t) {
for (int j = 1; j <= k; ++j) {
dp[i][j] = std::min(dp[i][j], dp[t][j - 1] + cost(t, i - 1));
}
}
}
return dp[n][k];
}
