#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/ioi/contests/ioi16d2/debug.h"
#else
#define debug(...) void(37)
#endif
long long take_photos(int N, int M, int K, std::vector<int> R_, std::vector<int> C) {
vector<array<int, 2>> ranges;
for (int i = 0; i < N; ++i) {
if (R_[i] - C[i] > 0) {
ranges.push_back({C[i], R_[i] + 1});
} else {
ranges.push_back({R_[i], C[i] + 1});
}
}
sort(ranges.begin(), ranges.end(), [&](auto x, auto y) {
return array<int, 2>{x[0], -x[1]} < array<int, 2>{y[0], -y[1]};
});
vector<int> L, R;
int mx_r = -1;
for (auto[l, r] : ranges) {
if (mx_r < r) {
mx_r = r;
L.push_back(l);
R.push_back(r);
}
}
N = int(L.size());
K = min(K, N);
auto S = [&](int x) {
return int64_t(x) * x;
};
int64_t inf = int64_t(M) * M;
vector<vector<int64_t>> best(N + 1, vector<int64_t>(K + 1, inf));
best[0][0] = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < K; ++j) {
for (int n = i; n < N; ++n) {
int64_t cost = best[i][j] + S(R[n] - L[i]) - (n + 1 < N && R[n] > L[n + 1] ? S(R[n] - L[n + 1]) : 0);
best[n + 1][j + 1] = min(best[n + 1][j + 1], cost);
}
}
}
int64_t ans = inf;
for (int i = 0; i <= K; ++i) ans = min(ans, best[N][i]);
return ans;
}
