#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int maxn = 1e5 + 100;
int a[maxn];
int b[maxn];
int c[maxn];
int pref[maxn];
int suf[maxn];
int r[maxn];
int l[maxn];
vector<int> v;
int get(int i, int j){
if(!i) return 0;
ll x = max(0, (- i + a[i] + j + a[j]) / 2);
return x * x;
}
ll f(int i){
return get(v[l[i-1]], v[r[i]]) - get(v[l[i-1]], v[i-1]) - get(v[i], v[r[i]]) + get(v[i], v[i-1]);
}
long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> c){
for(int i = 0; i < n; i++){
R[i]++; c[i]++;
int x = R[i] + c[i] - 1;
a[x] = max(a[x], abs(R[i] - c[i]) + 1);
}
for(int i = 1; i < m * 2; i++){
pref[i] = max(pref[i-1] - 1, a[i]);
}
for(int i = m * 2 - 1; i > 0; i--){
suf[i] = max(suf[i+1] - 1, a[i]);
}
ll ans = 0;
set<pll> mx;
for(int i = 1; i < m * 2; i++){
if(max(pref[i-1], suf[i+1]) <= a[i] && a[i]){
v.push_back(i);
// int p = v.size();
// v.push_back(i);
// l[p] = r[p] = p;
// if(p){
// ans -= get(v[p], v[p-1]);
// mx.insert({f(p) , p});
// }
// ans += get(i, i);
}
}
ans = get(v[0], v.back());
r[0] = v.size()-1; l[v.size()-1] = 0;
while(k--){
ll mx = -1;
vector<int> a;
for(int i = 0; i < v.size(); i = r[i] + 1){
for(int j = i; j < r[i]; j++){
ll x = get(v[i], v[r[i]]) - get(v[i], v[j]) - get(v[j+1], v[r[i]]) + get(v[j+1], v[j]);
if(mx < x){
mx = x;
a = {i, j, j + 1, r[i]};
}
}
}
if(mx == -1) break;
ans -= mx;
r[a[0]] = a[1];
l[a[1]] = a[0];
r[a[2]] = a[3];
l[a[3]] = a[2];
}
// for(int i = v.size(); i > k; i--){
// pll num = *mx.begin();
// mx.erase(num);
// ans += num.first;
// int b = num.second, a = l[b];
// int c = b + 1, d = r[c];
// if(a) mx.erase({f(a), a});
// if(d + 1 < v.size()) mx.erase({f(d+1), d+1});
// r[a] = d; l[d] = a;
// if(a) mx.insert({f(a), a});
// if(d + 1 < v.size()) mx.insert({f(d+1), d+1});
// ll mn = (ll)1e18, p;
// for(int i = 1; i < v.size(); i++){
// if(l[i] == i && f(i) < mn){
// mn = f(i);
// p = i;
// }
// }
// ans += mn;
// r[l[p-1]] = r[p];
// l[r[p]] = l[p-1];
// }
return ans;
}
