#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 20;
const long long max_cost = 1e12L + 20;
const long long inf = 1e18L + 20;
pair<int, int> ranges[maxN];
int L[maxN];
int R[maxN];
long long over[maxN];
pair<long long, int> dp[maxN];
int N, K;
void calc(long long cost) {
dp[0] = make_pair(0, 0);
for (int i = 1; i <= N; i++) {
dp[i] = make_pair(inf, -1);
for (int j = 1; j <= i; j++) {
dp[i] = min(dp[i], make_pair(dp[j - 1].first + 1LL * (R[i] - L[j]) * (R[i] - L[j]) - over[j] + cost, dp[j].second + 1));
}
}
}
long long take_photos(int _N, int M, int _K, vector<int> row, vector<int> col) {
N = _N;
K = _K;
for (int i = 1; i <= N; i++) {
if (row[i - 1] <= col[i - 1]) {
ranges[i].first = row[i - 1];
ranges[i].second = -col[i - 1];
}
else {
ranges[i].first = col[i - 1];
ranges[i].second = -row[i - 1];
}
}
sort(ranges + 1, ranges + N + 1);
int cnt = 0;
for (int i = 1; i <= N; i++) {
if (cnt == 0 || (L[cnt] != ranges[i].first && -ranges[i].second > R[cnt])) {
cnt++;
L[cnt] = ranges[i].first - 1;
R[cnt] = -ranges[i].second;
}
}
N = cnt;
for (int i = 2; i <= N; i++) {
if (R[i - 1] > L[i]) {
over[i] = 1LL * (R[i - 1] - L[i]) * (R[i - 1] - L[i]);
}
}
K = min(K, N);
long long lt = 0;
long long rt = max_cost;
long long res = inf;
while (lt <= rt) {
long long mt = (lt + rt) / 2;
calc(mt);
if (dp[N].second <= K) {
res = dp[N].first - mt * K;
rt = mt - 1;
}
else {
lt = mt + 1;
}
}
return res;
}
