#include "aliens.h"
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
using namespace std;
const ll N = 1e6 + 5;
int n, m, cntL[N], cntR[N], R[N];
pii dp[N];
vector<int> st[N], new_[N];
struct line{
ll k, b, cn;
};
double _(line a, line b) {
// a.k * x + a.b = b.k * x +
return (double)(a.b - b.b) / (b.k - a.k);
}
ll f(line c, int x) {
return ((ll)c.k * x + c.b);
}
ll check(ll c) {
deque<line> dq;
int mx = 0;
for(ll x = 1; x <= n; x++) {
dp[x] = {(ll)n * n + 5, 0};
if(cntL[x - 1] + cntR[x + 1] == m) dp[x] = dp[x - 1];
for(int j = 0; j < new_[x].size(); j++) {
int l = new_[x][j];
line a;
int r = R[l - 1];
a.b = dp[r].f - (ll)(r - l + 1) * (r - l + 1) + (ll)l * l + 1 - 2 * l;
a.k = -l; mx = max(mx, l);
assert(mx == l);
a.cn = -dp[r].s;
while(dq.size() >= 2) {
line cur = dq.back();
line prev = dq[(int)dq.size() - 2];
if(_(cur, prev) >= _(prev, a)) dq.pop_back();
else if(_(cur, prev) == _(prev, a) && cur.cn <= a.cn) dq.pop_back();
else break;
}
dq.push_back(a);
}
while(dq.size() >= 2) {
line cur = dq[0];
line nxt = dq[1];
if(f(nxt, 2 * x) < f(cur, 2 * x)) dq.pop_front();
else if(f(nxt, 2 * x) == f(cur, 2 * x) && nxt.cn >= cur.cn) dq.pop_front();
else break;
}
if(dq.size()) {
ll y = f(dq[0], 2 * x) + (ll)x * x + 2 * x + c;
dp[x] = min(dp[x], {y, -(dq[0].cn + 1)});
}
}
return -dp[n].s;
}
long long take_photos(int N, int M, int k, std::vector<int> r1, std::vector<int> c) {
swap(N, M);
m = M; n = N;
// vector<ll> l(m + 5);
int mnl = n, mxr = 0;
for(int i = 0; i < m; i++) {
if(c[i] > r1[i]) swap(c[i], r1[i]);
int l = min(r1[i], c[i]); r1[i] = max(r1[i], c[i]);
l++; r1[i]++;
cntL[r1[i]]++; cntR[l]++;
st[l].push_back(r1[i]);
mnl = min(l, mnl); mxr = max(mxr, r1[i]);
}
if(k == 1) {
return (ll)(mxr - mnl + 1) * (mxr - mnl + 1);
}
for(int i = 1; i <= n; i++) cntL[i] += cntL[i - 1];
for(int i = n; i >= 1; i--) cntR[i] += cntR[i + 1];
int C = 0;
for(int i = 1; i <= n; i++) {
C = max(C, i);
for(ll j = 0;j < st[i].size(); j++) {
C = max(C, st[i][j]);
}
R[i] = C;
new_[R[i - 1] + 1].push_back(i);
}
ll l = 0, r = 1e12, p = 0;
while(l <= r) {
ll mid = (l + r) / 2;
if(check(mid) >= k) {
p = mid;
l = mid + 1;
} else r = mid - 1;
}
check(p);
return dp[n].f - (ll)p * k;
}
