#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long int
const ll N = 1<<17;
ll dp[N], op[N], m[N], c[N], x[N], y[N], M, mx;
ll intersection(ll i, ll j){
ll A = c[j] - c[i], B = m[i] - m[j];
return A / B + (A % B != 0);
}
ll sqr(ll A){
return A * A;
}
pair<ll, ll> profit(ll n, ll Mid){
vector<ll> v = {0}, st = {0};
c[0] = x[1] * (x[1] - 2) + 1;
for (ll i=1;i<=n;i++){
ll l = 0, r = v.size();
while (l + 1 < r){
ll mid = (l + r) >> 1;
if (st[mid] <= y[i])
l = mid;
else
r = mid;
}
l = v[l];
dp[i] = dp[l] + sqr(y[i] - x[l + 1] + 1) + Mid;
op[i] = op[l] + 1;
if (i < n and x[i+1] <= y[i])
dp[i] -= sqr(y[i] - x[i+1] + 1);
c[i] = dp[i] + x[i+1] * (x[i+1] - 2) + 1;
while (v.size() > 1 and st.back() >= intersection(v.back(), i))
v.pop_back(), st.pop_back();
st.push_back(intersection(v.back(), i));
v.push_back(i);
}
return {dp[n], op[n]};
}
long long take_photos(int n, int mm, int k, vector<int> R, vector<int> C){
M = mm;
vector<pair<ll, ll>> vc;
for (ll i=0;i<n;i++){
if (R[i] > C[i])
swap(R[i], C[i]);
vc.push_back({R[i]+1, C[i]+1});
}
sort(begin(vc), end(vc));
n = 0;
for (auto [i, j] : vc){
if (j <= mx)
continue;
while (x[n] == i)
n--;
n++, x[n] = i, y[n] = j, mx = j;
}
for (ll i=1;i<=n;i++)
m[i-1] = -2 * x[i];
ll l = 0, r = M * M + 5;
while (l + 1 < r){
ll mid = (l + r) / 2;
if (profit(n, mid).second < k)
r = mid;
else
l = mid;
}
auto [a, b] = profit(n, l);
return a - k * l;
}
