#include <bits/stdc++.h>
long long INF = 2e9;
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
std::vector<std::vector<long long>> dp(n + 1, std::vector<long long>(k + 1, INF));
std::vector<std::pair<int, int>> segments(n), uniqueSegments;
auto cost = [&](int i, int j, bool positiveCheck=false) {
int r = segments[j].second;
int l = segments[i].first;
if (positiveCheck && r - l + 1 <= 0) {
return 0ll;
}
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) || ((a.first == b.first) && (a.second > b.second));
};
for (int i = 0; i < n; ++i) {
segments[i] = {std::min(r[i], c[i]), std::max(r[i], c[i])};
}
std::sort(segments.begin(), segments.end(), comparator);
int lastRb = -1;
for (int i = 0; i < n; ++i) {
if (segments[i].first >= lastRb && segments[i].second <= lastRb) {
continue;
}
lastRb = segments[i].second;
uniqueSegments.push_back(segments[i]);
}
std::swap(segments, uniqueSegments);
n = segments.size();
for (int i = 0; i <= k; ++i) {
dp[0][i] = 0;
}
for (int i = 1; i <= n; ++i) {
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) - cost(t, t - 1, true /*positive check*/));
}
}
}
return dp[n][k];
}
