#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 20;
const long long inf = 1e18L + 20;
const long long max_cost = 1e12L + 20;
pair<int, int> ranges[maxN];
int L[maxN];
int R[maxN];
long long over[maxN];
pair<long long, int> dp[maxN];
int N, K;
struct line {
long long a, b, cnt;
line(): a(0), b(0), cnt(0) {};
line(long long _a, long long _b, int _cnt): a(_a), b(_b), cnt(_cnt) {};
long long eval(int x) {
return a * x + b;
}
};
long long floor_div(long long a, long long b) {
return a / b;
}
long long inter(line L1, line L2) {
return floor_div(L2.b - L1.b, L1.a - L2.a);
}
struct CHT {
vector<line> Q;
int pt = 0;
void add(line L) {
while ((int)Q.size() >= 2 && inter(Q.end()[-2], Q.back()) >= inter(Q.back(), L)) {
Q.pop_back();
}
Q.push_back(L);
}
line get(int x) {
pt = min(pt, (int)Q.size() - 1);
while (pt + 1 < (int)Q.size() && Q[pt].eval(x) > Q[pt + 1].eval(x)) {
pt++;
}
return Q[pt];
}
};
void calc(long long cost) {
CHT C;
dp[0] = make_pair(0, 0);
C.add(line(-2 * L[1], 1LL * L[1] * L[1] - over[1] + cost, 0));
for (int i = 1; i <= N; i++) {
auto best = C.get(R[i]);
dp[i].first = best.eval(R[i]) + 1LL * R[i] * R[i];
dp[i].second = best.cnt + 1;
if (i == N) {
break;
}
C.add(line(-2 * L[i + 1], dp[i].first + 1LL * L[i + 1] * L[i + 1] - over[i + 1] + cost, dp[i].second));
}
}
long long take_photos(int _N, int M, int _K, vector<int> row, vector<int> col) {
N = _N;
K = _K;
for (int i = 1; i <= N; i++) {
if (row[i - 1] <= col[i - 1]) {
ranges[i].first = row[i - 1];
ranges[i].second = -col[i - 1];
}
else {
ranges[i].first = col[i - 1];
ranges[i].second = -row[i - 1];
}
}
sort(ranges + 1, ranges + N + 1);
int cnt = 0;
for (int i = 1; i <= N; i++) {
if (cnt == 0 || (L[cnt] != ranges[i].first && -ranges[i].second > R[cnt])) {
cnt++;
L[cnt] = ranges[i].first - 1;
R[cnt] = -ranges[i].second;
}
}
N = cnt;
for (int i = 2; i <= N; i++) {
if (R[i - 1] > L[i]) {
over[i] = 1LL * (R[i - 1] - L[i]) * (R[i - 1] - L[i]);
}
}
K = min(K, N);
long long lt = 0;
long long rt = max_cost;
long long res = inf;
while (lt <= rt) {
long long mt = (lt + rt) / 2;
calc(mt);
if (dp[N].second <= K) {
res = dp[N].first - mt * K;
rt = mt - 1;
}
else {
lt = mt + 1;
}
}
return res;
}
