#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> filter_dominated(vector<pair<int, int>> I)
{
vector<pair<int, int>> J = {{INT_MIN, INT_MIN}};
sort(I.begin(), I.end(), [](pair<int, int> lhs, pair<int, int> rhs) {
return lhs.first != rhs.first ? lhs.first < rhs.first : lhs.second > rhs.second;
});
for(auto [l, r] : I)
if(not (J.back().first <= l and r <= J.back().second))
J.emplace_back(l, r);
J.erase(J.begin());
return J;
}
constexpr int64_t square(int64_t x) { return x*x; }
int64_t take_photos(int _n, int _m, int _k, vector<int> r, vector<int> c)
{
size_t n = _n, m = _m, k = _k; (void)m;
vector<pair<int, int>> intervals;
for(size_t i = 0; i < n; i++)
intervals.emplace_back(min(r[i], c[i]), max(r[i], c[i]));
intervals = filter_dominated(intervals);
n = intervals.size();
vector<vector<int64_t>> cost(n+1, vector<int64_t>(k+1, INT64_MAX / 3));
cost[0] = vector<int64_t>(k+1, 0);
for(size_t i = 1; i <= n; i++)
{
for(size_t l = 1; l <= k; l++)
{
for(size_t j = 0; j < i; j++)
{
auto x = intervals[i-1].second - intervals[j].first + 1,
y = max(0, (j ? intervals[j-1].second : -1) - intervals[j].first + 1);
cost[i][l] = min(cost[i][l], cost[j][l-1] + square(x) - square(y)) ;
}
}
}
return cost[n][k];
}
#ifdef XHOVA
int main()
{
cout << take_photos(5, 7, 2, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6}) << endl;
cout << take_photos(2, 6, 2, {1, 4}, {4, 1}) << endl;
}
#endif
