#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, pair<pll, pll>> ppll;
const ll inf = 1e18;
pll united_loc(pll a, pll b){
return {min(a.first, b.first), max(a.second, b.second)};
}
ll calc_difference(pll a, pll b){
ll big_dist = max(a.second, b.second) - min(a.first, b.first), small_dist = min(a.second, b.second) - max(a.first, b.first);
return big_dist * big_dist - a.second * a.second - b.second * b.second + small_dist * small_dist;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
ll cnt = 0;
vector<ll> v(m);
for(ll i = 0; i < n; i++) v[r[i]] = max(v[r[i]], (ll)abs(r[i] - c[i]) + 1);
set<pll> s;
ll ans = 0;
for(ll i = 0; i < n; i++) s.insert({r[i], v[r[i]]}), ans += v[r[i]] * v[r[i]];
// cout << ans << "\n";
while(s.size() > k){
pll prev = {-1, -1};
ppll mi = {inf, {{-1, -1}, {-1, -1}}};
for(pll i : s){
if(prev.first != -1) mi = min(mi, {calc_difference(prev, i), {prev, i}});
prev = i;
}
auto[x, p] = mi;
auto[a, b] = p;
s.erase(a); s.erase(b);
s.insert(united_loc(a, b));
ans += x;
// cout << x << "\n";
}
return ans;
}
