#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
typedef long long ll;
#define F first
#define S second
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define pb push_back
const int N = 1e5+5, M = 1e6+1;
pair<ll, int> dp[N];
vector<int> R[M];
struct Line {
mutable ll k, m, p, cnt;
bool operator<(const Line &o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
// (for doubles, use inf = 1/.0, div(a, b) = a / b)
// (for minimum, insert -k and -m and return -ans)
static const ll inf = LLONG_MAX;
ll div(ll a, ll b) {
return a / b - ((a ^ b) < 0 && a % b);
}
bool isect(iterator x, iterator y) {
if(y == end()) return x -> p = inf, 0;
if(x -> k == y -> k) x -> p = x -> m > y -> m ? inf : -inf;
else x -> p = div(y -> m - x -> m, x -> k - y -> k);
return x -> p >= y -> p;
}
void add(ll k, ll m, ll ctr) {
k = -k;
m = -m;
//cout << k << " " << m << " " << ctr << " huh\n";
auto z = insert({k, m, 0, ctr}), y = z++, x = y;
while(isect(y, z)) z = erase(z);
if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
while((y = x) != begin() && (--x) -> p >= y -> p) isect(x, erase(y));
}
pair<ll, int> query(ll x) {
assert(!empty());
auto l = *lower_bound(x);
//cout << l.k << " " << l.m << " " << l.cnt << " " << x << " ez\n";
return {-(l.k * x + l.m), l.cnt+1ll};
}
};
ll l[N], r[N];
long long take_photos(int n, int m, int k, std::vector<int> roo, std::vector<int> co) {
vector<ll> ro, c;
for (auto &i : roo)ro.push_back(i);
for (auto &i : co)c.push_back(i);
vector<pair<ll, ll>> rng;
for (int i = 0; i < n; i++) {
ll l = min(ro[i], c[i]), rr = max(ro[i], c[i]);
R[rr].push_back(l);
}
int mnl = 1e9;
for (int i = m; i >= 0; i--) {
sort(all(R[i]));
for (auto &l : R[i]) {
if (mnl > l)rng.push_back({l, i});
mnl = min(mnl, l);
}
R[i].clear();
}
sort(all(rng));
n = sz(rng);
k = min(k, sz(rng));
ll st = 0, ed = ll(m) * ll(m), ans = 1e18;
for (int i = 0; i < n; i++) {
l[i] = rng[i].F;
r[i] = rng[i].S;
}
while (st <= ed) {
ll md = (st + ed) / 2ll;
LineContainer LC;
for (int i = 0; i < n; i++) {
ll cc = 0;
if (i) {
ll xx = max(0ll, r[i-1]-l[i]+1);
cc = dp[i-1].F - (xx * xx);
}
//cout << "bad: " << 2ll * l[i] << " " << -2ll * l[i] + (l[i] * l[i]) + cc << "\n";
LC.add(-2ll * l[i], -2ll * l[i] + (l[i] * l[i]) + cc, (i == 0 ? 0 : dp[i-1].S));
pair<ll, int> xx = LC.query(r[i]);
dp[i] = {md + (r[i] * r[i]) + (2ll * r[i]) + 1ll + xx.F, xx.S};
//cout << md << " " << dp[i].F << " ez2\n";
}
if (dp[n-1].S <= k) {
ans = min(ans, dp[n-1].F - md * dp[n-1].S);
ed = md - 1;
} else {
st = md + 1;
}
}
/*int cur = 0, prv = 1;
for (int i = 0; i < n; i++) {
l[i] = rng[i].F, r[i] = rng[i].S;
dp[i][cur] = (r[i] - l[0] + 1ll) * (r[i] - l[0] + 1ll);
//cout << l[i] << " " << r[i] << " " << dp[i][cur] << " ez\n";
}
for (int ii = 0; ii+1 < k; ii++) {
cur ^= 1;
prv ^= 1;
LineContainer LC;
for (int i = 0; i <= ii; i++) {
ll cc = 0;
if (i) {
ll xx = max(0ll, r[i-1]-l[i]+1);
cc = dp[i-1][prv] - (xx * xx);
}
LC.add(-2ll * l[i], -2ll * l[i] + (l[i] * l[i]) + cc);
dp[i][cur] = dp[i][prv];
//cout << l[i] << " " << r[i] << " " << dp[i][cur] << " ez\n";
}
for (int i = ii+1; i < n; i++) {
ll cc = 0;
if (i) {
ll xx = max(0ll, r[i-1]-l[i]+1);
cc = dp[i-1][prv] - (xx * xx);
}
LC.add(-2ll * l[i], -2ll * l[i] + (l[i] * l[i]) + cc);
dp[i][cur] = (r[i] * r[i]) + (2ll * r[i]) + 1ll + LC.query(r[i]);
//cout << l[i] << " " << r[i] << " " << dp[i][cur] << " ez\n";
}
}*/
return ans;
}
