#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<long long, long long>
#define st first
#define nd second
//#define endl "\n"
#define sp " "
#define N 50005
#define ll long long
vector<pii> o;
ll dp[N][105], M;
const ll INF = 2e18 + 7;
ll dist(int x, int y){
ll h = M - (x + y - 2);
h = max((ll)0, h);
return h * h;
}
ll cost(int i, int j){
if (i > j) swap(i, j);
pii x = o[i], y = o[j];
ll prv = 0;
if (i > 1) prv = dist(max(x.st, o[i - 1].st), max(x.nd, o[i - 1].nd));
ll curr = dist(min(x.st, y.st), min(x.nd, y.nd)) - prv;
return curr;
}
void f(int cnt, int l, int r, int sl, int sr){
if (l > r) return;
int mid = (l + r) / 2;
pii best = {INF, INF};
for (int i = sl; i <= min(sr, mid); i++){
best = min(best, {cost(i, mid) + dp[cnt - 1][i - 1], i});
}
ll opt = best.nd;
dp[cnt][mid] = best.st;
f(cnt, l, mid - 1, sl, opt);
f(cnt, mid + 1, r, opt, sr);
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<pii> p;
M = m;
for (int i = 0; i < n; i++)
{
r[i]++, c[i]++;
int tmp = r[i];
r[i] = c[i];
c[i] = m - tmp + 1;
if (r[i] + c[i] > m + 1){
int tmp = r[i];
r[i] = m + 1 - c[i];
c[i] = m + 1 - tmp;
}
p.pb({r[i], c[i]});
}
sort(p.begin(), p.end());
pii last = {0, m + 5};
for (auto i : p){
if (i.nd < last.nd){
o.pb(i);
last = i;
}
}
o.pb({m + 1, 0});
reverse(o.begin(), o.end());
int gh = o.size();
for (int i = 1; i < gh; i++){
dp[1][i] = cost(1, i);
}
for (int i = 2; i <= k; i++)
{
f(i, 1, gh - 1, 1, gh - 1);
}
return dp[k][o.size() - 1];;
}
