#include <bits/stdc++.h>
using namespace std;
int N;
vector<pair<int, int>> points;
long long calc(int a, int b, int largest) {
long long cost = ((long long) (b - a + 1)) * (b - a + 1);
if (largest > a) {
cost -= ((long long) (largest - a + 1)) * (largest - a + 1);
}
return cost;
}
long long dp(int i, int largest, int k) {
if (k == 1) {
return calc(points[i].first, points[N - 1].second, largest);
}
long long best = numeric_limits<long long>::max();
for (int j = i; j < N - k + 1; j++) {
best = min(
best,
calc(points[i].first, points[j].second, largest) + dp(j + 1, points[j].second, k - 1)
);
}
return best;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<pair<int, int>> all_points = vector<pair<int, int>>(n);
for (int i = 0; i < n; i++) {
cout << i << endl;
int b = min(r[i], c[i]);
int e = max(r[i], c[i]);
all_points[i] = make_pair(b, -e);
}
sort(all_points.begin(), all_points.end());
points = vector<pair<int, int>>();
points.push_back(make_pair(all_points[0].first, -all_points[0].second));
int largest = -all_points[0].second;
for (int i = 1; i < n; i++) {
cout << i << endl;
if (largest >= -all_points[i].second) {
continue;
}
largest = -all_points[i].second;
points.push_back(make_pair(all_points[i].first, -all_points[i].second));
}
N = points.size();
return dp(0, 0, k > N ? N : k);
}
