#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;
const ll inf = 1e18;
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<pair<int,int>> A;
pair<ll,ll> solve(ll x){
int sz = A.size();
for (int i = 0; i < sz; i++){
dp[i] = inf;
for (int j = 0; j <= i; j++){
ll Q = A[i].second-A[j].first+1;
ll Cost = Q*Q;
ll Add = 0;
ll cnt = 1;
if (j != 0){
cnt += pd[j-1];
Add += dp[j-1];
int r = A[j].first, c = A[j-1].second;
ll P = max(0,(c-r+1));
Add -= P*P;
}
if (make_pair(Cost+Add+x,cnt) < make_pair(dp[i],pd[i]))
dp[i] = Cost+Add+x, pd[i] = cnt, opt[i] = j;
}
}
for (int i = 0; i < sz-1; i++)
assert(opt[i] <= opt[i+1]);
return {dp[sz-1],pd[sz-1]};
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
::n = n, ::m = m, ::k = k;
for (int i = 0; i < n; i++)
if (r[i] > c[i])
swap(r[i],c[i]);
vector<pair<int,int>> Tmp;
for (int i = 0; i < n; i++)
Tmp.push_back({r[i],c[i]});
sort(Tmp.begin(),Tmp.end());
for (int i = 0; i < n; i++){
if (!A.empty() and A.back().first == Tmp[i].first){
A.pop_back();
A.push_back(Tmp[i]);
}
else if (A.empty() or A.back().second < Tmp[i].second)
A.push_back(Tmp[i]);
}
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;
}
