#include "aliens.h"
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 0
#define TEST if(test)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e12;
const int MAX_N = 100000;
int N, M, K;
vector<pii> vt;
vector<ll> C;
ll dp[MAX_N+1];
bool sf(pii a, pii b){
if(a.first==b.first){
return a.second>b.second;
}
return a.first<b.first;
}
/*struct Lichao{
struct NODE{
int l, r;
ll a, b;
};
ll SZ;
vector<NODE> seg;
void add(){
seg.pb({-1, -1, 0, INFLL});
}
void Init(int x){
SZ = (ll)x;
add();
init(0, 0LL, SZ);
}
void Reset(){
for(int i=0; i<seg.size(); i++){
seg[i].a = 0LL; seg[i].b = INFLL;
}
}
void init(int idx, ll s, ll e){
if(s==e) return;
seg[idx].l = seg.size(); add();
seg[idx].r = seg.size(); add();
init(seg[idx].l ,s, (s+e)/2); init(seg[idx].r, (s+e)/2+1, e);
}
void Update(ll a, ll b){
update(0, 0LL, SZ, a, b);
}
void update(int idx, ll s, ll e, ll x, ll y){
if(s*x+y<=seg[idx].a*s+seg[idx].b && e*x+y<=seg[idx].a*e+seg[idx].b){
seg[idx].a = x;
seg[idx].b = y;
return;
}else if(s*x+y>=seg[idx].a*s+seg[idx].b && e*x+y>=seg[idx].a*e+seg[idx].b){
return;
}
update(seg[idx].l, s, (s+e)/2, x, y);
update(seg[idx].r, (s+e)/2+1, e, x, y);
}
ll Calc(ll x){
return calc(0, 0LL, SZ, x);
}
ll calc(int idx, ll s, ll e, ll k){
if(s==e){
return seg[idx].a * k + seg[idx].b;
}
if(k<=(s+e)/2){
return min(seg[idx].a * k + seg[idx].b, calc(seg[idx].l, s, (s+e)/2, k));
}else{
return min(seg[idx].a * k + seg[idx].b, calc(seg[idx].r, (s+e)/2+1, e, k));
}
}
}Seg;*/
struct S{
ll a, b;
int idx;
};
vector<S> st;
int idx = 0;
void add(ll a, ll b, int i){
while(st.size()>=2){
S prv = st.back(); st.pop_back();
if((b-prv.b) * (prv.a - st.back().a) >= (a-prv.a) * (prv.b - st.back().b)){
if(idx==st.size()) idx--;
continue;
}else{
st.pb(prv);
break;
}
}
st.pb({a, b, i});
}
int cnt[MAX_N+1];
ll calc(ll x, int i){
while(idx+1<st.size()){
if(st[idx+1].a * x + st[idx+1].b < st[idx].a * x + st[idx].b) idx++;
else break;
}
cnt[i] = cnt[st[idx].idx]+1;
return st[idx].a * x + st[idx].b;
}
int solve(ll x){
//TEST cout<<x<<endl;
st.clear();
idx = 0;
for(int i=0; i<vt.size(); i++){
//TEST cout<<dp[i]<<" ";
add(-4LL * (ll)vt[i].first, dp[i] - 2LL * C[i] + 2LL * (ll)vt[i].first * (ll)vt[i].first, i);
dp[i+1] = 2LL * (ll)vt[i].second * (ll)vt[i].second + calc((ll)vt[i].second, i+1) + x;
}//TEST cout<<dp[vt.size()]<<endl<<cnt[vt.size()]<<endl<<dp[vt.size()] - (ll)cnt[vt.size()] * x<<endl<<endl;
return cnt[vt.size()];
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
N = n; M = m; K = k;
for(int i=0; i<N; i++){
vt.pb({min(r[i], c[i]), max(r[i], c[i]) + 1});
}
sort(vt.begin(), vt.end(), sf);
int mx = -1;
for(int i=0 ;i<N; i++){
if(mx>=vt[i].second){
vt[i].second = INF;
vt[i].first = INF;
}else mx = max(mx, vt[i].second);
}
sort(vt.begin(), vt.end());
while(!vt.empty() && vt.back().first==INF && vt.back().second==INF) vt.pop_back();
C.pb(0LL);
for(int i=1; i<vt.size(); i++){
C.pb(max(0LL, (ll)(vt[i-1].second - vt[i].first)) * max(0LL, (ll)(vt[i-1].second - vt[i].first)));
}
ll s = 0, e = (ll)M*(ll)M, mid;
while(s<e){
mid = (s+e)/2LL;
int t = solve(2LL*mid+1LL);
if(t<=K){
e = mid;
}else{
s = mid+1LL;
}
}
solve(2LL*s);
return (dp[vt.size()] - 2LL * s * (ll)K)/2LL;
}
