#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
const int MAXN = 1e6 + 10;
pii p[MAXN];
ll d[MAXN], intersect[MAXN], slope[MAXN];
ll better[MAXN];
int cnt[MAXN];
vector<pii> vec;
int sec[MAXN], sz;
ll eval(int id, ll x) {
return intersect[id] + slope[id] * x;
}
ll get_time(int a, int b) {
return (intersect[b] - intersect[a]) / (slope[a] - slope[b]) + 1;
}
void add_cand(int id) {
intersect[id] = d[id] + 1ll*vec[id].F*vec[id].F;
if (id && vec[id-1].S > vec[id].F)
intersect[id] -= 1ll*(vec[id-1].S - vec[id].F) * (vec[id-1].S - vec[id].F);
slope[id] = -2ll*vec[id].F;
while (sz > 1 && get_time(sec[sz-2], id) < get_time(sec[sz-2], sec[sz-1])) sz--;
better[sz] = sz==0? -1ll: get_time(sec[sz-1], id);
sec[sz++] = id;
}
pair<ll, int> get(ll mid) {
int n = vec.size();
d[0] = cnt[0] = 0;
sz = 0;
for (int i = 0; i < n; i++) {
add_cand(i);
int pos = lower_bound(better, better + sz, vec[i].S) - better;
if (pos == sz || better[pos] > vec[i].S) pos--;
d[i+1] = 1ll*vec[i].S*vec[i].S + eval(sec[pos], vec[i].S) + mid;
cnt[i+1] = 1 + cnt[sec[pos]];
}
//cout << d[n] << " " << cnt[n] << " " << mid << endl;
return {d[n], cnt[n]};
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
for (int i = 0; i < n; i++) {
p[i] = {r[i], c[i]};
if (p[i].F > p[i].S)
swap(p[i].F, p[i].S);
p[i].S++;
}
sort(p, p + n, [](pii a, pii b) {
if (a.F ^ b.F)
return a.F < b.F;
return a.S > b.S;
});
vec.clear();
for (int i = 0; i < n; i++)
if (vec.empty() || vec.back().S < p[i].S)
vec.push_back(p[i]);
//for (auto x: vec)
// cout << x.F << " " << x.S << endl;
n = vec.size();
k = min(n, k);
ll lo = -1, hi = 1ll*m*m;
while (hi-lo>1){
ll mid = hi+lo>>1;
if (get(mid).S > k)
lo = mid;
else
hi = mid;
}
auto x = get(hi);
return x.F - 1ll*(k - x.S) * hi;
}
/*
int main() {
//cout << take_photos(5, 7, 2, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6}) << "\n";
//cout << take_photos(2, 6, 2, {1, 4}, {4, 1}) << "\n";
//cout << take_photos(3, 10, 1, {0, 0, 1}, {0, 1, 0}) << "\n";
return 0;
}*/
