#include "aliens.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define x first
#define y second
ll sq(ll a) { return a * a; }
bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.x == b.x) return (a.y > b.y);
return a.x < b.x;
}
ll dp[100001], cnt[100001];
vector<pair<int, int>> useful = {{0, 0}};
int N;
bool case1(int i, int j, int k) {
return (2 * useful[k].y * (useful[j + 1].x - useful[i + 1].x) >=
dp[j] - dp[i] + sq(useful[j + 1].x - 1) - sq(useful[i + 1].x - 1) -
sq(max(0, useful[j].y - useful[j + 1].x + 1)) +
sq(max(0, useful[i].y - useful[i + 1].x + 1)));
}
bool case2(int i, int j, int k) {
return ((dp[k] - dp[j] + sq(useful[k + 1].x - 1) - sq(useful[j + 1].x - 1) -
sq(max(0, useful[k].y - useful[k + 1].x + 1)) +
sq(max(0, useful[j].y - useful[j + 1].x + 1))) *
(useful[j + 1].x - useful[i + 1].x) <
(dp[j] - dp[i] + sq(useful[j + 1].x - 1) - sq(useful[i + 1].x - 1) -
sq(max(0, useful[j].y - useful[j + 1].x + 1)) +
sq(max(0, useful[i].y - useful[i + 1].x + 1))) *
(useful[k + 1].x - useful[j + 1].x));
}
void compute(ll lambda, int k) {
deque<int> dq;
dq.push_back(0);
for (int i = 1; i <= N; i++) {
while (dq.size() > 1 && case1(dq[0], dq[1], i)) dq.pop_front();
int opt = dq.front();
dp[i] = sq(useful[i].y - useful[opt + 1].x + 1) + dp[opt] -
sq(max(0, useful[opt].y - useful[opt + 1].x + 1)) + lambda;
cnt[i] = cnt[opt] + 1;
while (dq.size() > 1 && case2(dq[dq.size() - 2], dq.back(), i)) dq.pop_back();
dq.push_back(i);
// cout << opt << ' ' << dp[i] << ' ' << dp[i] - lambda * cnt[i] << ' ' << cnt[i] << '\n';
}
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<pair<int, int>> points;
for (int i = 0; i < n; i++) {
int x = r[i], y = c[i];
if (x > y) swap(x, y);
points.push_back({x + 1, y + 1});
}
sort(points.begin(), points.end(), cmp);
for (int i = 0; i < n; i++)
if (useful.back().y < points[i].y) useful.push_back(points[i]);
N = useful.size() - 1;
ll l = 0, u = (ll)m * m;
while (l != u) {
ll mid = (l + u) / 2;
// cout << l << ' ' << u << " |\n";
compute(mid, k);
// cout << '\n';
if (cnt[N] > k) l = mid + 1;
else u = mid;
}
compute(l, k);
return dp[N] - l * cnt[N];
}
