#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
typedef long long ll;
ll n, m;
vector<pair<ll, ll>> p;
ll getVal(vector<ll> &dp, vector<ll> &k, ll &pen, int &i, int j) {
if (j <= 0)
return (p[i].first + p[0].second + 2 - m)
* (p[i].first + p[0].second + 2 - m) + pen;
j--;
if (p[i].first + p[j+1].second + 2 - m > (p[i].first - p[j].first))
return (p[i].first + p[j+1].second + 2 - m) * (p[i].first - p[j].first) * 2
- (p[i].first - p[j].first) * (p[i].first - p[j].first) + pen + dp[j];
else
return (p[i].first + p[j+1].second + 2 - m)
* (p[i].first + p[j+1].second + 2 - m) + pen + dp[j];
}
pair<ll, ll> solve(ll pen) {
vector<ll> dp(n, 1ll << 62ll);
vector<ll> k(n, 1);
dp[0] = (p[0].first + p[0].second + 2 - m)
* (p[0].first + p[0].second + 2 - m) + pen;
for (int i = 1; i < n; i++) {
for (int j = 0; j <= i; j++) {
ll val = getVal(dp, k, pen, i, j);
ll valK = j == 0 ? 1 : (k[j-1] + 1);
if (val < dp[i] || (val <= dp[i] && valK < k[i])) {
dp[i] = val;
k[i] = valK;
}
}
}
return {k[n-1], dp[n-1]};
}
ll take_photos(int n1, int m1, int k, vector<int> r, vector<int> c) {
// Sort and filter
n = n1; m = m1;
vector<pair<ll, ll>> prs(n);
for (int i = 0; i < n; i++) {
if (r[i] > c[i]) prs[i] = {r[i], m-1-c[i]};
else prs[i] = {c[i], m-1-r[i]};
}
sort(prs.begin(), prs.end());
p.clear();
for (auto &e : prs) {
while (!p.empty() && p.back().second <= e.second) p.pop_back();
p.push_back(e);
}
n = p.size();
// Solve
ll left = 0, right = (ll)m * (ll)m;
while (left < right) {
ll mid = (left + right) / 2;
pair<ll, ll> val = solve(mid);
if (val.first > k) {
left = mid + 1;
}
else {
right = mid;
}
}
pair<ll, ll> res = solve(left);
return res.second - k*left;
}
