#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
const int N = 100005;
int n, m, k;
pair<int, int> segs[N];
pair<ll, int> dp[N];
void check(ll mid){
deque<pair<pair<ll, ll>, int>> dq;
dq.push_back({{1ll*segs[0].f*segs[0].f-2*segs[0].f, -2*segs[0].f}, 0});
for(int i = 0; i<n; ++i){
while(dq.size()>1 && pair<ll, int>{dq[1].f.f+dq[1].f.s*segs[i].s, dq[1].s}<pair<ll, int>{dq[0].f.f+dq[0].f.s*segs[i].s, dq[0].s})
dq.pop_front();
dp[i] = {dq[0].f.f+dq[0].f.s*segs[i].s+1ll*segs[i].s*segs[i].s+1+2*segs[i].s+mid, dq[0].s+1};
if(i==n-1) break;
ll a = dp[i].f-max(0ll, segs[i].s-segs[i+1].f+1ll)*max(0ll, segs[i].s-segs[i+1].f+1ll)+1ll*segs[i+1].f*segs[i+1].f-2*segs[i+1].f;
ll b = -2*segs[i+1].f;
while(dq.size()>1 && (double)(a-dq[dq.size()-1].f.f)/(dq[dq.size()-1].f.s-b)<(double)(a-dq[dq.size()-2].f.f)/(dq[dq.size()-2].f.s-b))
dq.pop_back();
dq.push_back({{a, b}, dp[i].s});
}
}
ll take_photos(int _n, int _m, int _k, vector<int> _r, vector<int> _c){
n = _n, m = _m, k = _k;
vector<pair<int, int>> _tmp, tmp;
for(int i = 0; i<n; ++i)
_tmp.push_back({_r[i], _c[i]});
for(int i = 0; i<n; ++i)
if(_tmp[i].f>_tmp[i].s)
swap(_tmp[i].f, _tmp[i].s);
sort(_tmp.begin(), _tmp.end(), [&](pair<int, int> a, pair<int, int> b){
if(a.f != b.f) return a.f<b.f;
return a.s>b.s;
});
for(auto [l, r] : _tmp)
if(tmp.empty() || r>tmp.back().s)
tmp.push_back({l, r});
n = tmp.size();
for(int i = 0; i<n; ++i)
segs[i] = tmp[i];
ll lo = 0, hi = 1ll*m*m;
while(lo<hi){
ll mid = lo+(hi-lo)/2; check(mid);
if(dp[n-1].s<=k) hi = mid;
else lo = mid+1;
} check(lo);
return dp[n-1].f-lo*k;
}
