#include "aliens_c.h"
#define N 100000
#define INF 0x3f3f3f3f3f3f3f3f
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int aa[N], bb[N];
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = aa[ii[j]] != aa[i_] ? aa[ii[j]] - aa[i_] : bb[i_] - bb[ii[j]];
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
long long dp[N + 1], xx[N + 1], yy[N + 1]; int kk[N + 1];
long long cross(int i, int j, int k) {
return (xx[j] - xx[i]) * (yy[k] - yy[i]) - (xx[k] - xx[i]) * (yy[j] - yy[i]);
}
long long dot(long long x1, long long y1, long long x2, long long y2) {
return x1 * x2 + y1 * y2;
}
long long eval(int i, long long x) {
return xx[i] * x - yy[i];
}
void solve(int *ii, int n, long long c) {
static int qu[N + 1];
int i, head, cnt;
dp[0] = 0, kk[0] = 0;
xx[0] = aa[ii[0]], yy[0] = dp[0] + (long long) aa[ii[0]] * aa[ii[0]];
head = cnt = 0;
qu[head + cnt++] = 0;
for (i = 1; i <= n; i++) {
int b = bb[ii[i - 1]];
while (cnt >= 2 && eval(qu[head], b * 2) < eval(qu[head + 1], b * 2))
head++, cnt--;
dp[i] = -eval(qu[head], b * 2) + (long long) b * b + c, kk[i] = kk[qu[head]] + 1;
if (i < n) {
int a = aa[ii[i]];
if (b > a)
dp[i] -= (long long) (b - a) * (b - a);
xx[i] = a, yy[i] = dp[i] + (long long) a * a;
while (cnt >= 2 && cross(qu[head + cnt - 2], qu[head + cnt - 1], i) <= 0)
cnt--;
qu[head + cnt++] = i;
}
}
}
long long take_photos(int n, int m, int k, int *rr, int *cc) {
static int ii[N];
int n_, i;
long long lower, upper;
for (i = 0; i < n; i++) {
int tmp;
aa[i] = rr[i], bb[i] = cc[i];
if (aa[i] > bb[i])
tmp = aa[i], aa[i] = bb[i], bb[i] = tmp;
bb[i]++;
ii[i] = i;
}
sort(ii, 0, n);
n_ = 0;
for (i = 0; i < n; i++)
if (n_ == 0 || bb[ii[n_ - 1]] < bb[ii[i]])
ii[n_++] = ii[i];
n = n_;
lower = -1, upper = (long long) m * m + 1;
while (upper - lower > 1) {
long long c = (lower + upper) / 2;
solve(ii, n, c);
if (kk[n] <= k)
upper = c;
else
lower = c;
}
solve(ii, n, upper);
return dp[n] - upper * k;
}
