#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];
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 (up[i][u] && X(T[up[i][u]], T[up[0][up[i][u]]]) > x)
u = up[i][u];
}
if (u && X(T[up[0][u]], T[u]) > x) u = up[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;
int MN[m+1]; fill(MN, MN+m+1, 1e9);
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 j = i-1;
MN[i] = mn[i], up[0][i] = i-1;
while (j >= MN[i]) {
MN[i] = min(MN[i], MN[j]);
j = (MN[j] == 1e9 ? j-1 : MN[j]-1);
}
T[i-1] = {(ld)-2*(i-1), dp[i] - i * i + 2 * i * (i-1)}; C[i-1] = C[i];
int u = mn[i]-1;
int op = f(i, u);
dp[i] = T[op].f(i) + i * i + mid, C[i] = C[op]+1;
for (int j = LOG-1; j >= 0; --j) {
if (X(T[up[0][up[j][u]]], T[i-1]) <= X(T[up[0][up[j][u]]], T[up[j][u]])) u = up[j][u];
}
if (u && X(T[up[0][u]], T[i-1]) <= X(T[up[0][u]], T[u])) u = up[0][u];
up[0][i-1] = u;
for (int j = 1; j < LOG; ++j) up[j][i-1] = up[j-1][up[j-1][i-1]];
// if (mid == 1.5625 && i == 4) {
// cout << up[0][i] << ' ' << T[i-1].k << ' ' << T[i-1].c << '\n';
// }
}
}
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[up[0][up[j][I]]], T[i]) <= X(T[up[0][up[j][I]]], T[up[j][I]])) I = up[j][I];
}
if (I && X(T[up[0][I]], T[i]) <= X(T[up[0][I]], T[I])) I = up[0][I];
up[0][i] = I;
for (int j = 1; j < LOG; ++j) up[j][i] = up[j-1][up[j-1][i]], up[j][i] = up[j-1][up[j-1][i]];
}
// cout << mid << ' ' <<
// if (mid == 1.5625) {
// for (int i = 1; i <= m; ++i) {
// cout << up[0][i] << ' ' << MN[i] << '\n';
// }
// }
if (C[m] <= k)
R = mid, ans = dp[m] - k * mid;
else
L = mid;
}
return roundl(ans);
}
