#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5, maxm = 1e6 + 5;
int n, m, k;
int Cmq[maxm][20];
ll dp[maxm], pd[maxm], opt[maxm];
int get(int l, int r){
int len = (r-l+1);
len = log2(len);
return min(Cmq[l][len], Cmq[r-(1<<len)+1][len]);
}
vector<int> a;
pair<ll,ll> solve(ll x){
int last = -1;
for (int Iti = 0; Iti < a.size(); Iti++){
int i = a[Iti];
int Len = (i-get(0, i)+1);
dp[i] = 1LL*(Len)*(Len)+x, pd[i] = 1, opt[i] = -1;
for (int Itj = 0; Itj < Iti; Itj++){
int j = a[Itj];
int minLen = get(j+1,i);
int myLen = get(j,j);
if (myLen > minLen)
continue;
ll Q = (i-minLen+1);
ll P = max(0,(j-minLen+1));
ll now = dp[j] + 1LL*Q*Q - 1LL*P*P + x;
if (make_pair(now,pd[j]+1) <= make_pair(dp[i],pd[i]))
dp[i] = now, pd[i] = pd[j]+1, opt[i] = j;
}
last = opt[i];
}
for (int i = m-1; i >= 1; i--)
if (get(i,i) < m)
return {dp[i],pd[i]};
return {dp[0],pd[0]};
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
memset(Cmq, 63, sizeof Cmq);
::n = n, ::m = m, ::k = k;
for (int i = 0; i < n; i++){
if (r[i] > c[i])
swap(r[i],c[i]);
a.push_back(c[i]);
}
sort(a.begin(), a.end());
a.resize(unique(a.begin(),a.end())-a.begin());
for (int i = 0; i < n; i++)
Cmq[c[i]][0] = min(Cmq[c[i]][0], r[i]);
for (int i = 1; i < 20; i++)
for (int j = 0; j+(1<<(i-1)) < m; j++)
Cmq[j][i] = min(Cmq[j][i-1], Cmq[j+(1<<(i-1))][i-1]);
ll lo = -1, hi = 1e12 + 1;
while (hi-lo > 1){
ll mid = (lo+hi) >> 1;
if (solve(mid).second > k)
lo = mid;
else
hi = mid;
}
auto it = solve(hi);
return it.first - hi*k;
}
