#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, long long> pil;
typedef pair<ll, ll> pll;
#define BB dq[dq.size() - 2]
struct Line {
ll cf, b, z;
Line(ll cf_, ll b_, ll z_) {
cf = cf_;
b = b_;
z = z_;
}
};
inline pll inter(Line a, Line b) { return pll(a.b - b.b, b.cf - a.cf); }
inline bool cmp(pll a, pll b) {
if (a.second < 0) {
a.second *= -1;
a.first *= -1;
}
if (b.second < 0) {
b.second *= -1;
b.first *= -1;
}
return a.first * b.second <= a.second * b.first;
}
inline bool cmp(pll a, ll b) { return cmp(a, pll(b, 1)); }
inline bool equ(pll a, ll b) {
return !cmp(a, pll(b, 1)) && !cmp(pll(b, 1), a);
}
ll take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
vi ind;
int N = 0;
{
rep(i, 0, n) {
if (r[i] > c[i]) swap(r[i], c[i]);
c[i]++;
}
vi local(n);
iota(all(local), 0);
sort(all(local), [&](int a, int b) {
if (r[a] != r[b]) return r[a] < r[b];
return c[a] > c[b];
});
int mx = -1;
rep(i, 0, n) if (c[local[i]] > mx) {
ind.pb(local[i]);
mx = c[local[i]];
}
N = ind.size();
ind.pb(n);
r.push_back(1e9);
if (k == 1) {
ll dist = c[ind[N - 1]] - r[ind[0]];
return dist * dist;
}
}
auto solve = [&](ll Cost) -> pil {
vector<pil> dp(N + 1);
deque<Line> dq;
dp[N] = pil(0, 0);
auto push = [&](int id) {
int pos = ind[id];
int pre = ind[id - 1];
ll Rj1 = c[pre];
ll Li = r[pos];
Line ln(
Rj1,
dp[id].second + Rj1 * Rj1 - (Li < Rj1 ? (Rj1 - Li) * (Rj1 - Li) : 0),
dp[id].first);
while (dq.size() > 1 && cmp(inter(BB, ln), inter(BB, dq.back())))
dq.pop_back();
dq.pb(ln);
return;
};
auto relax = [&](int id) {
ll pn = -2ll * r[ind[id]];
while (dq.size() > 1) {
if (cmp(inter(dq[0], dq[1]), pn)) {
dq.pop_front();
} else
break;
}
return;
};
for (int i = N - 1; ~i; i--) {
push(i + 1);
relax(i);
int me = ind[i];
dp[i] = pil(dq[0].z + 1, (1ll * r[me] * r[me]) - 2ll * r[me] * dq[0].cf +
dq[0].b + Cost);
}
return dp[0];
};
ll lo = 1ll * m * m + 10, hi = -1;
while (lo - 1 != hi) {
ll mid = lo + hi >> 1;
if (k <= solve(mid).first)
hi = mid;
else
lo = mid;
}
auto result = solve(lo);
return result.second - k * lo;
}
