#pragma once
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef std::complex<ll> point;
#define x real
#define y imag
const ll INF = 1e18;
ll dot(point a, point b) {
return (std::conj(a) * b).x();
}
ll cross(point a, point b) {
return (std::conj(a) * b).y();
}
std::vector<point> hull, vecs;
std::vector<int> cnth;
void add_line(ll slope, ll y_intercept, int cnt) {
point new_line({slope, y_intercept});
while(!vecs.empty() && dot(vecs.back(), new_line - hull.back()) < 0) {
hull.pop_back();
vecs.pop_back();
cnth.pop_back();
}
if(!hull.empty()) {
vecs.push_back(point({0, 1}) * (new_line - hull.back()));
}
hull.push_back(new_line);
cnth.push_back(cnt);
}
pair<ll, int> get(ll x_value) {
point to_query = point({x_value, 1});
int index = lower_bound(vecs.begin(), vecs.end(), to_query, [](point a, point b) {
return cross(a, b) > 0;
}) - vecs.begin();
ll val = dot(to_query, hull[index]);
int mx = cnth[index];
return {val, mx};
}
long long take_photos(int n, int m, int k, std::vector<int> rr, std::vector<int> cc) {
vector<array<int, 2>> intervals;
for(int i = 0; i < n; i++) {
if(rr[i] > cc[i]) swap(rr[i], cc[i]);
intervals.push_back({rr[i], cc[i]});
}
sort(intervals.begin(), intervals.end(), [](array<int, 2> a, array<int, 2> b) {
if(a[0] == b[0]) return a[1] > b[1];
return a[0] < b[0];
});
vector<array<int, 2>> intervals2;
vector<ll> l, r;
for(int i = 0; i < n; i++) {
if(i == 0 || intervals[i][0] < intervals2.back()[0] || intervals[i][1] > intervals2.back()[1]) {
intervals2.push_back(intervals[i]);
l.push_back(intervals[i][0]);
r.push_back(intervals[i][1]);
}
}
n = intervals2.size();
auto works = [&](ll lambda, ll& ans) {
hull.clear();
vecs.clear();
cnth.clear();
vector<ll> dp(n + 1);
vector<int> cnt(n + 1);
for(int i = 1, j = 0; i <= n; i++, j++) {
ll slope = 2 * (l[j] - 1);
ll intercept = ((l[j] - 1) * (l[j] - 1) + dp[j]);
if(j > 0) {
ll mx = max(0LL, r[j - 1] - l[j] + 1);
intercept -= mx * mx;
}
add_line(slope, intercept, cnt[j]);
auto gg = get(-r[j]);
dp[i] = gg.first + r[j] * r[j] + lambda;
cnt[i] = gg.second + 1;
}
ans = dp[n];
return cnt[n] <= k;
};
ll lo = 0, hi = 1LL * m * m, ans = INF;
while(lo < hi) {
ll mid = lo + (hi - lo) / 2;
if(works(mid, ans)) {
hi = mid;
} else {
lo = mid + 1;
}
}
works(hi, ans);
return ans - k * hi;
}
