#include<bits/stdc++.h>
#ifdef HOME
#else
#include "aliens.h"
#endif
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define Time (double)clock()/CLOCKS_PER_SEC
bool comp(ii a, ii b) {
return a.f < b.f || (a.f == b.f && a.s > b.s);
}
const int N = 1e5 + 7, INF = 1e18 + 7, C = 1e12;
struct Line {
int a, b, k;
};
ii get(Line l, int x) {
return mp(l.a + l.b * x, l.k);
}
int get_better(Line a, Line b) {
if (a.a >= b.a)
return -INF;
int d = a.b - b.b;
return (b.a - a.a + d - (a.k >= b.k)) / d;
}
struct Cht {
vector <Line> a;
int ptr;
void clear() {
a.clear();
ptr = 0;
}
void add(ii l, int k) {
Line add = {l.f, l.s, k};
while (a.size() >= 2 && get_better(add, a.back()) <= get_better(a.back(), a[a.size() - 2]))
a.pop_back();
while (a.size() && add.a >= a.back().a)
a.pop_back();
a.app(add);
}
ii get_cht(int x) {
if (ptr == a.size())
return mp(-INF, -INF);
while (ptr + 1 < a.size() && get(a[ptr + 1], x) > get(a[ptr], x))
++ptr;
return get(a[ptr], x);
}
} mem;
ii dp[N];
ii solve(int n, int sh, vector <ii> &a) {
dp[0] = mp(0, 0);
mem.clear();
for (int i = 1; i <= n; ++i) {
if (i == 1 || a[i - 2].s < a[i - 1].f) {
mem.add(mp(-dp[i - 1].f - a[i - 1].f * a[i - 1].f, 2 * a[i - 1].f), -dp[i - 1].s);
}
else {
int in = a[i - 2].s - a[i - 1].f + 1;
mem.add(mp(-dp[i - 1].f - a[i - 1].f * a[i - 1].f + in * in, 2 * a[i - 1].f), -dp[i - 1].s);
}
dp[i] = mem.get_cht(a[i - 1].s + 1);
dp[i].f *= -1; dp[i].s *= -1;
dp[i].f += (a[i - 1].s + 1) * (a[i - 1].s + 1) + sh;
dp[i].s += 1;
/*
for (int l = 0; l < i; ++l) {
int tl = a[l].f, tr = a[i - 1].s;
int len = tr - tl + 1;
if (l && a[l - 1].s >= tl) {
int in = a[l - 1].s - tl + 1;
dp[i] = min(dp[i], mp(dp[l].f + len * len - in * in + sh, dp[l].s + 1));
}
}
*/
}
return dp[n];
}
long long take_photos(signed n, signed m, signed k, vector<signed> rr, vector<signed> cc) {
vector <ii> a;
for (int i = 0; i < n; ++i) {
if (cc[i] < rr[i])
swap(rr[i], cc[i]);
a.app(mp(rr[i], cc[i]));
}
sort(all(a), comp);
vector <ii> b;
int r = -1;
for (auto e : a) {
if (e.s <= r)
continue;
b.app(e);
r = e.s;
}
a = b;
n = a.size();
if (k >= n)
return solve(n, 0, a).f;
int l = -C;
r = C;
while (l < r - 1) {
int mid = (l + r) / 2;
if (solve(n, mid, a).s <= k)
r = mid;
else
l = mid;
}
auto t = solve(n, r, a);
return t.f - k * r;
}
