#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pint = pair<int, int>;
#define x first
#define y second
const int maxn = 100004;
const lint inf = (lint)4.29e12;
vector<pint> ra, a;
lint m[maxn];
int p[maxn];
lint sq(int x) { return x*(lint)x; }
lint cost(int x, int y) {
lint ret = sq(a[y].y - a[x+1].x + 1);
if (x>=0 and a[x].y >= a[x+1].x) ret -= sq(a[x].y - a[x+1].x + 1);
return ret;
}
void fill_dp(int s, int e, int l, int r, lint x) {
if (s>e) return;
int k = (s+e)/2;
for (int i=l; i<k and i<r; i++) {
lint now = cost(i, k) + x;
if (i>=0) now += m[i];
if (m[k] < now) m[k] = now, p[k] = i;
}
fill_dp(s, k-1, l, p[k], x);
fill_dp(k+1, e, p[k], r, x);
}
int f(lint k) {
fill(m, m+maxn, -inf);
fill_dp(0, a.size()-1, -1, a.size()-1, k);
int ret = 0;
for (int i=a.size()-1; ~i; i=p[i]) ret++;
return ret;
}
lint take_photos(int n, int M, int k, vector<int> R, vector<int> c) {
for (int i=0; i<n; i++) ra.emplace_back(min(R[i], c[i]), max(R[i], c[i]));
sort(ra.begin(), ra.end(), [](pint a, pint b) { return a.x < b.x or (a.x == b.x and a.y > b.y); });
int mx = 0;
for (pint& i : ra) {
if (i.y <= mx) continue;
mx = i.y;
a.push_back(i);
}
lint l = 0, r = inf;
while (l+1<r) {
lint m = (l+r) / 2;
if (f(m) > k) r = m;
else l = m;
}
k = f(l);
return m[a.size()-1] - l * k;
}
