#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define fi first
#define se second
/*
Suppose the penalty for using another picture is +y
*/
pll solve_lambda_brute(const vpll& pts, ll y) {
ll np = pts.size();
// note: stores NEGATIVE area, num pictures
// then, the DP just gets the maximum state
vpll dp(np, {0ll, 0ll});
for(ll i = 0ll; i < np; i++) {
ll cl = pts[i].fi, cr = pts[i].se;
dp[i] = {-(cr - pts[0ll].fi + 1ll) * (cr - pts[0ll].fi + 1ll) - y, 1ll};
for(ll j = 1ll; j <= i; j++) {
ll overlap = max(pts[j - 1ll].se - pts[j].fi + 1ll, 0ll);
pll cand = {dp[j - 1ll].fi + overlap * overlap -(cr - pts[j].fi + 1ll) * (cr - pts[j].fi + 1ll) - y, dp[j - 1ll].se + 1ll};
if(cand > dp[i]) dp[i] = cand;
}
}
return dp[np - 1ll];
}
ll take_photos(int i_n, int i_m, int i_k, vi r, vi c) {
ll n = i_n, m = i_m, k = i_k;
// first, we preprocess. remove all redundant points
vpll pts;
for(ll i = 0ll; i < n; i++) {
if(r[i] > c[i]) swap(r[i], c[i]);
pts.push_back({r[i], c[i]});
}
sort(pts.begin(), pts.end(), [](pll p1, pll p2){return p1.fi < p2.fi || (p1.fi == p2.fi && p1.se > p2.se);});
ll max_r = -1ll;
vpll filt_pts;
for(ll i = 0ll; i < n; i++) {
ll cl = pts[i].fi, cr = pts[i].se;
if(cr > max_r) {
filt_pts.push_back(pts[i]);
// cerr << cl << " " << cr << endl;
max_r = cr;
}
}
// Performing lagrangian relaxation
ll lo = 0ll, hi = 1e12;
while(hi - lo > 1ll) {
ll mid = (lo + hi) >> 1ll;
pll cpair = solve_lambda_brute(filt_pts, mid);
ll c_val = cpair.fi, c_k = cpair.se;
if(c_k >= k) lo = mid;
else hi = mid;
}
return -(solve_lambda_brute(filt_pts, lo).fi + k * lo);
}
