#include <bits/stdc++.h>
#include "aliens.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long
#define sz(x) (int) x.size()
const int N = 100'005;
const ll inf = 1e18;
array<ll, 2> dp[N];
ll take_photos(int n, int crap, int m, vector<int> R, vector<int> C) {
array<ll, 2> a[n + 1];
vector<ll> v;
for (int i = 1; i <= n; i++) {
a[i] = {R[i - 1], C[i - 1]};
if (a[i][0] > a[i][1]) swap(a[i][0], a[i][1]);
}
sort(a + 1, a + n + 1);
ll prf[n + 2]{};
prf[1] = -1e18;
for (int i = 1; i <= n; i++) {
prf[i + 1] = max(prf[i], a[i][1]);
a[i][0]--;
prf[i] = max(prf[i], a[i][0]);
}
auto check = [&] (ll c) {
for (int i = 1; i <= n; i++) {
dp[i] = {inf, inf};
}
dp[0] = {0, 0};
for (int i = 1; i <= n; i++) {
ll mx = -inf;
for (int k = i; k >= 1; k--) {
mx = max(mx, a[k][1]);
ll cost = (mx - prf[k]) * (mx + prf[k] - 2 * a[k][0]) + c;
if (cost < 0) continue;
array<ll, 2> val = dp[k - 1];
val[0] += cost;
val[1]++;
dp[i] = min(dp[i], val);
}
}
return dp[n][1] <= m;
};
ll l = 0, r = inf;
while (l <= r) {
ll md = ((l + r) >> 1);
if (check(md)) {
r = md - 1;
} else {
l = md + 1;
}
}
ll k = l;
check(k);
return dp[n][0] - k * m;
}
