#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int M = 1e6 + 5, LOG = 20;
int up[LOG][M], up2[LOG][M];
deque<int> dq;
ld dp[M], C[M];
struct line {
ld k, c;
ld f(ld x) {
return k * x + c;
};
} T[M];
ld X(line &A, line &B) {
return (ld)(A.c - B.c) / (B.k - A.k);
}
int f(int x, int u) {
for (int i = LOG-1; i >= 0; --i) {
if (up2[i][u] && X(T[up2[i][u]], T[up2[0][up2[i][u]]]) > x)
u = up2[i][u];
}
if (u && X(T[up2[0][u]], T[u]) > x) u = up2[0][u];
return u;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
int mn[m+1];
fill(mn, mn+m+1, 1e9);
for (int i = 0; i < n; ++i) r[i]++, c[i]++;
for (int i = 0; i < n; ++i) mn[max(r[i], c[i])] = min({mn[max(r[i], c[i])], r[i], c[i]});
ld L = 0, R = m * (1ll) * m, ans = 1e18;
for (int _ = 0; _ < 200; ++_) {
ld mid = (L + R)/2;
T[0] = {0, 0}, dq = {0}, C[0] = 0;
for (ll i = 1; i <= m; ++i) {
if (mn[i] != 1e9) {
if (mn[i] == i) {
int op = f(i, i-1);
dp[i] = T[op].f(i) + i * i + mid, up[0][i] = i-1, C[i] = C[op]+1;;
}
else {
int u = i-1;
for (int j = LOG-1; j >= 0; --j) {
if (up[j][u] >= mn[i]) u = up[j][u];
}
int op = f(i, up[0][u]);
dp[i] = T[op].f(i) + i * i + mid, up[0][i] = u, C[i] = C[op]+1;
T[u] = {(ld)-2*u, dp[i] - i * i + 2 * i * u}; C[u] = C[i];
int U = up2[0][u];
for (int j = LOG-1; j >= 0; --j) {
if (X(T[up2[0][up2[j][U]]], T[u]) <= X(T[up2[0][up2[j][U]]], T[up2[j][U]])) U = up2[j][U];
}
up2[0][u] = U;
for (int j = 1; j < LOG; ++j) up2[j][u] = up2[j-1][up2[j-1][u]];
}
}
else
dp[i] = dp[i-1], C[i] = C[i-1], up[0][i] = i-1;
T[i] = {(ld)-2*i, dp[i] - i * i + 2 * i * i};
int I = up[0][i];
for (int j = LOG-1; j >= 0; --j) {
if (X(T[up2[0][up2[j][I]]], T[i]) <= X(T[up2[0][up2[j][I]]], T[up2[j][I]])) I = up2[j][I];
}
if (I && X(T[up2[0][I]], T[i]) <= X(T[up2[0][I]], T[I])) I = up2[0][I];
up2[0][i] = I;
for (int j = 1; j < LOG; ++j) up2[j][i] = up2[j-1][up2[j-1][i]], up[j][i] = up[j-1][up[j-1][i]];
}
if (C[m] <= k)
R = mid, ans = dp[m] - k * mid;
else
L = mid;
}
return roundl(ans);
}
