#include "aliens.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <climits>
#include <complex>
// using namespace std;
// using ll = long long;
// typedef complex<ll> point;
// #define x real
// #define y imag
// ll sq(ll a) {
// return a * a;
// }
// ll sq(int a) {
// return (ll)(a) * a;
// }
// // ll getArea(pair<ll, ll> a) {
// // return sq(a.second - a.first + 1);
// // }
// // ll getArea(ll a, ll b) {
// // return sq(b - a + 1);
// // }
// ll positiveArea(ll a, ll b) {
// ll sideLength = b - a + 1;
// return (sideLength > 0 ? sq(sideLength) : 0);
// }
// ll dot(point a, point b) {
// return ((conj(a) * b).x());
// }
// ll cross(point a, point b) {
// return ((conj(a) * b).y());
// }
// vector<point> hull, vec;
// vector<ll> countHull;
// void addLine(ll m, ll c, ll count) {
// point newLine({m, c});
// while (!vec.empty() && (dot(vec.back(), newLine - hull.back()) < 0)) {
// vec.pop_back();
// hull.pop_back();
// countHull.pop_back();
// }
// if (!hull.empty()) vec.push_back(point({0, 1}) * (newLine - hull.back()));
// countHull.push_back(count);
// hull.push_back(newLine);
// }
// pair<ll, ll> query(ll ri) {
// point toFind({ri, 1});
// ll idx = lower_bound(vec.begin(), vec.end(), toFind, [](point a, point b) {return (cross(a, b) > 0);}) - vec.begin();
// return {dot(toFind, hull[idx]), countHull[idx]};
// }
// ll take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
// vector<pair<ll, ll>> oriPoints, points;
// for (ll i = 0; i < n; ++i) {
// if (r[i] > c[i]) swap(r[i], c[i]);
// oriPoints.emplace_back(r[i], c[i]);
// }
// sort(oriPoints.begin(), oriPoints.end());
// pair<ll, ll> cur = oriPoints[0];
// for (ll i = 1; i < n; ++i) {
// if (oriPoints[i].first == cur.first) cur.second = max(oriPoints[i].second, cur.second);
// else if (cur.second < oriPoints[i].second) {
// if (cur.first != -1) points.emplace_back(cur);
// cur = oriPoints[i];
// }
// }
// points.emplace_back(cur);
// int newN = points.size();
// auto check = [&] (ll cost, ll &res) {
// hull.clear(); vec.clear(); countHull.clear();
// vector<ll> dp(newN + 1, 0), counts(newN + 1, 0);
// for (int i = 1; i <= newN; ++i) {
// ll m = 2 * (points[i - 1].first - 1), c = sq(points[i - 1].first - 1) + dp[i - 1] + (i > 1 ? positiveArea(points[i - 1].first, points[i - 2].second) : 0);
// addLine(m, c, counts[i - 1]);
// auto cur = query(-points[i - 1].second);
// dp[i] = cur.first + cost + sq(points[i - 1].second);
// counts[i] = cur.second + 1;
// }
// res = dp[newN];
// return (counts[newN] <= k);
// };
// ll low = 0, high = sq(m), res = LLONG_MAX / 2;
// while (low < high) {
// ll mid = (low + high) / 2;
// if (check(mid, res)) high = mid;
// else low = mid + 1;
// }
// check(low, res);
// return (res - k * low);
// }
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();
// cout << lambda << '\n';
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]);
// cout << slope << ' ' << intercept << ' ';
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;
// cout << dp[i] << ' ' << cnt[i] << '\n';
}
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;
}
