#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, [&] (array<ll, 2> x, array<ll, 2> y) {return make_pair(x[0], -x[1]) < make_pair(y[0], -y[1]);});
multiset<ll> s;
vector<array<ll, 2>> a = {{0, 0}};
for (int i = 1; i <= n; i++) {
while (s.size() && *s.begin() < A[i][0]) s.erase(s.begin());
if (s.size() && A[i][1] <= *s.rbegin()) continue;
a.push_back({A[i][0], A[i][1]});
s.insert(A[i][1]);
}
n = a.size() - 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]);
a[i][0] *= -2;
}
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++) {
for (int k = i; k >= 1; k--) {
ll cost = a[i][1] * a[k][0] - prf[k] * (prf[k] + a[k][0]);
array<ll, 2> val = dp[k - 1];
val[0] += cost;
val[1]++;
dp[i] = min(dp[i], val);
}
dp[i][0] += a[i][1] * a[i][1] + c;
}
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;
}
