#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define COL first
#define ROW second
vector<pair<ll,ll>> pts, dp;
pair<ll,ll> eval(int i, int j, ll cost)
{
ll new_square = (pts[i].COL - pts[j+1].ROW);
ll overlap = max(pts[j].COL - pts[j+1].ROW, 0LL);
ll total_area = new_square * new_square - overlap * overlap;
return {dp[j].first + total_area + cost, dp[j].second + 1};
}
pair<ll,ll> calc(int n, ll cost)
{
deque<int> cht;
dp[0] = {0, 0};
for (int i = 1; i <= n; i++)
{
dp[i] = {LLONG_MAX, LLONG_MAX};
for (int j = 0; j < i; j++)
dp[i] = min(dp[i], eval(i, j, cost));
}
return dp[n];
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
vector<pair<ll,ll>> temp_pts(n);
for (int i = 0; i < n; i++)
{
if (r[i] > c[i])
swap(r[i], c[i]);
temp_pts[i] = {c[i], r[i] - 1};
}
sort(temp_pts.begin(), temp_pts.end());
pts.push_back({0, 0});
for (pair<ll,ll> pt : temp_pts)
{
while (!pts.empty() && pts.back().ROW >= pt.ROW)
pts.pop_back();
pts.push_back(pt);
}
n = pts.size() - 1;
dp.resize(n + 1);
ll lo = 0, hi = 1e12, mid;
while (lo < hi)
{
mid = (lo + hi) / 2;
calc(n, mid);
if (dp[n].second > k)
lo = mid + 1;
else
hi = mid;
}
calc(n, lo);
return dp[n].first - k * lo;
}
