#include <bits/stdc++.h>
#include "aliens.h"
#define pb push_back
#define F0R(var) for (; (var) > 0; --(var))
#define endl '\n'
template<typename... Ts>
void debug_out(const Ts&... ts) {
std::cerr << "DEBUG:";
if constexpr (sizeof...(Ts) > 0) {
((std::cerr << ' ' << ts), ...);
}
std::cerr << '\n';
}
#define f first
#define FINOUT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0)
#define s second
#define debug(...) debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<long long, long long> pii;
typedef vector<long long> vi;
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
vector<int> maxR(m + 1);
iota(all(maxR), -1);
for(long long i = 0; i < n; i++) {
if(r[i] > c[i])
swap(r[i], c[i]);
r[i]++, c[i]++;
maxR[r[i]] = max(maxR[r[i]], c[i]);
}
int mx = 0;
vector<pii> intervals;
intervals.push_back({0, 0});
for(int i = 1; i <= m; i++) {
if(maxR[i] < i || maxR[i] <= mx)
continue;
mx = maxR[i];
intervals.push_back({i, mx});
}
n = intervals.size();
vector<pii> dp(n + 1, {1e13, 1});
long long ini = 0, mid, end = 1e13, ans;
vector<pii> v;
v.push_back({0, 0});
auto getBest = [&](int x) -> int {
return (--lower_bound(all(v), pii{x + 1, 0}))->second;
};
auto w = [&](int j, int i) -> pii {
int sz = (intervals[i].s - intervals[j + 1].f + 1);
int overlap = (intervals[j + 1].f <= intervals[j].s ? intervals[j].s - intervals[j + 1].f + 1 : 0);
return {dp[j].f + 1LL * sz * sz + mid - 1LL * overlap * overlap, dp[j].s + 1};
};
while(ini <= end) {
mid = (ini + end) / 2;
fill(all(dp), pii{1e13, 1});
dp[0] = {0, 0};
for(int i = 1; i < n; i++) {
int best = getBest(i);
dp[i] = w(best, i);
for(int j = (int)v.size() - 1; j >= 0; j--) {
auto [x, old_best] = v[j];
if(x > i && w(old_best, x) >= w(i, x))
v.pop_back();
else {
int ini = max((int)x, i + 1), mid, end = n, ans = n + 1;
while(ini <= end) {
mid = (ini + end)/2;
if(w(old_best, mid) >= w(i, mid)) {
ans = min(ans, mid);
end = mid - 1;
}
else ini = mid + 1;
}
if(ans == x)
v.pop_back();
if(ans != n + 1)
v.push_back({ans, i});
break;
}
}
}
if(dp[n - 1].s <= k) {
ans = dp[n - 1].f - 1LL * k * mid;
end = mid - 1;
}
else ini = mid + 1;
}
return ans;
}
// int32_t main() {
// cout << take_photos(5, 7, 2, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6}) << endl;
// }
