#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
#define ll long long
const ll MAXN = 1e5 + 100;
#define pii pair<ll, ll>
#define fi first
#define se second
struct inv{
ll l; ll r;
};
struct line{
ll m; ll c; ll cnt;
ll getY(ll x){
return m * x + c;
}
} cht[MAXN];
ll l = 0, r = 1;
bool betterLine(line& a, line& b, line& c){
ll lhs = (c.c - a.c) * (a.m - b.m), rhs = (b.c - a.c) * (a.m - c.m);
return lhs < rhs || (lhs == rhs && c.cnt < b.cnt);
}
bool betterQue(line& a, line& b, ll x){
ll lhs = a.getY(x), rhs = b.getY(x);
return lhs > rhs || (lhs == rhs && b.cnt < a.cnt);
}
void insertLine(line L){
while(r - l >= 2 && betterLine(cht[r - 2], cht[r - 1], L))r--;
cht[r++] = L;
}
pii query(ll x){
while(r - l >= 2 && betterQue(cht[l], cht[l + 1], x))l++;
return {cht[l].getY(x), cht[l].cnt};
}
vector<inv> v, grid;
bool cmpGrid(inv& a, inv& b){
return a.l < b.l || (a.l == b.l && a.r > b.r);
}
void buildVector(){
sort(grid.begin(), grid.end(), cmpGrid);
ll sz = grid.size(); inv prev = {-1, -1};
for(ll i = 0; i < sz; i++){
if(grid[i].r > prev.r){
v.push_back(grid[i]); prev = grid[i];
}
}
}
void initcht(){
cht[0] = {-2 * v[0].l + 2, (v[0].l - 1) * (v[0].l - 1), 0};
l = 0, r = 1;
}
ll memo[MAXN], cnt[MAXN];
pii dp(ll val, ll n){
memo[0] = cnt[0] = 0;
initcht();
for(ll i = 1; i <= n; i++){
pii queAns = query(v[i-1].r);
memo[i] = queAns.fi + v[i-1].r * v[i-1].r + val;
cnt[i] = queAns.se + 1;
if(i < n){
ll m = -2 * v[i].l + 2, maxim = max((ll)0, (ll)(v[i-1].r - v[i].l + 1));
ll c = memo[i] - maxim * maxim + (v[i].l - 1) * (v[i].l - 1);
insertLine({m, c, cnt[i]});
}
}
return {memo[n], cnt[n]};
}
ll take_photos(int a, int b, int c, vector<int> R, vector<int> C) {
ll n = (ll)a, m = (ll)b, k = (ll)c;
for(ll i = 0; i < n; i++){
grid.push_back({(ll)min(R[i], C[i]), (ll)max(R[i], C[i])});
}
buildVector();
ll l = 0, r = 1e12, ans = 0;
while(l <= r){
ll mid = (l + r) >> 1;
pii val = dp(mid, v.size());
if(val.se <= k){
ans = val.fi - k * mid, r = mid - 1;
}
else l = mid + 1;
}
return ans;
}
