#include "bits/extc++.h"
using namespace std;
template <typename T>
void dbgh(const T& t) {
cerr << t << endl;
}
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t << " | ";
dbgh(u...);
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr \
if (false) \
cerr
#endif
using ll = long long;
#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())
int n;
vector<pair<int, int>> arr;
long sq(long x) {
return x * x;
}
pair<long, int> solve(long x) {
pair<long, int> dp[n + 1];
dp[n] = {0, 0};
for (int i = n - 1; i >= 0; i--) {
dp[i] = {long(4e18), 0};
for (int j = i; j < n; j++) {
auto [a, b] = dp[j + 1];
dp[i] = min(dp[i], pair<long, int> {
a + sq(arr[j].second - arr[i].first + 1) + x,
b + 1});
}
if (i && arr[i].first <= arr[i - 1].second) {
dp[i].first -= sq(arr[i - 1].second - arr[i].first + 1);
}
}
return dp[0];
}
ll take_photos(int _n, int, int k, vector<int> a1, vector<int> a2) {
n = _n;
for (int i = 0; i < n; i++) {
arr.emplace_back(min(a1[i], a2[i]), max(a1[i], a2[i]));
}
sort(begin(arr), end(arr), [&](pair<int, int> a, pair<int, int> b) -> bool {
if (a.first == b.first) {
return a.second > b.second;
}
return a.first < b.first;
});
vector<pair<int, int>> narr;
int mx = -1;
for (auto& [l, r] : arr) {
if (r > mx) {
mx = r;
narr.emplace_back(l, r);
}
}
swap(arr, narr);
n = sz(arr);
for (int i = 0; i < n - 1; i++) {
assert(arr[i].first < arr[i + 1].first &&
arr[i].second < arr[i + 1].second);
}
long l = 0, r = 1e18;
while (l < r) {
long mid = (l + r) / 2;
if (solve(mid).second <= k) {
r = mid;
} else {
l = mid + 1;
}
}
auto [x, cnt] = solve(l);
dbg(l, cnt);
return x - k * l;
}
