#include <bits/stdc++.h>
using namespace std;
long long take_photos(int n, int m, int k, vector<int> r, vector<int> l) {
for (int i = 0; i < n; i++) {
if (r[i] < l[i]) {
swap(r[i], l[i]);
}
}
vector<int> ind(n);
iota(ind.begin(), ind.end(), 0);
sort(ind.begin(), ind.end(), [&](int i, int j) {
return l[i] < l[j] || (l[i] == l[j] && r[i] > r[j]);
});
int mx = INT_MIN;
ind.erase(remove_if(ind.begin(), ind.end(), [&](int i) {
if (r[i] <= mx) {
return true;
} else {
mx = r[i];
return false;
}
}), ind.end());
int sz = (int) ind.size();
sort(ind.begin(), ind.end(), [&](int i, int j) {
return r[i] < r[j];
});
k = min(k, sz);
vector<pair<long long, long long>> lines;
auto add_line = [&](long long m, long long c) -> void {
while (lines.size() > 1) {
auto [m1, c1] = lines[(int) lines.size() - 1];
auto [m2, c2] = lines[(int) lines.size() - 2];
//(c - c2) / (m2 - m) >= (c1 - c2) / (m2 - m1)
if ((c - c2) * (m2 - m1) >= (c1 - c2) * (m2 - m)) {
lines.pop_back();
} else {
break;
}
}
lines.emplace_back(m, c);
};
auto query = [&](long long x) -> long long {
int lo = 0, hi = (int) lines.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
auto [m1, c1] = lines[mid + 1];
auto [m2, c2] = lines[mid];
//x <= (c1 - c2) / (m2 - m1)
if (x * (m2 - m1) <= c1 - c2) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lines[lo].first * x + lines[lo].second;
};
vector<int> new_r(sz), new_l(sz);
for (int i = 0; i < sz; i++) {
new_r[i] = r[ind[i]];
new_l[i] = l[ind[i]];
}
r.swap(new_r);
l.swap(new_l);
vector<long long> dp(sz);
long long ans = LLONG_MAX;
for (int j = 1; j <= k; j++) {
lines.clear();
add_line(2 * r[sz - j], (long long)-r[sz - j] * r[sz - j] - (j == 1 ? 0 : dp[sz - j + 1]));
for (int i = sz - j; i >= 0; i--) {
long long old_dp = dp[i];
dp[i] = (long long)(l[i] - 1) * (l[i] - 1) - query(l[i] - 1);
if (j != 1 && i > 0) {
add_line(2 * r[i - 1], (long long)-r[i - 1] * r[i - 1] - old_dp);
}
}
ans = min(ans, dp[0]);
}
return ans;
}
