#include "aliens.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
using ll = long long;
struct Line {
ll m = 0, c = 0;
Line(ll _m, ll _c) : m(_m), c(_c) { }
ll get(ll x) { return m * x + c; }
double intersection(Line o) { return (double) (o.c - c) / (double) (m - o.m); }
bool good(Line l2, Line l3) { return __int128(l2.c - c) * (l2.m - l3.m) < __int128(l3.c - l2.c) * (m - l2.m); }
};
struct CHT {
deque<Line> hull;
void insert(Line l) {
while (hull.size() > 1) {
auto last = hull.end()[-1];
auto p_last = hull.end()[-2];
if (p_last.good(last, l)) break;
hull.pop_back();
}
hull.push_back(l);
}
ll query(ll x) {
while (hull.size() > 1 && hull[0].get(x) > hull[1].get(x)) {
hull.pop_front();
}
return hull[0].get(x);
}
};
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<pair<int, int>> a;
for (int i = 0; i < n; i++) {
r[i]++, c[i]++;
a.push_back({min(r[i], c[i]) - 1, max(r[i], c[i])});
}
sort(a.begin(), a.end(), [&](auto i, auto j) {
if (i.first != j.first) return i.first < j.first;
return i.second > j.second;
});
{
vector<pair<int, int>> final;
auto last = make_pair(-1, -1);
for (int i = 0; i < n; i++) {
auto [x, y] = a[i];
if (x >= last.first && y <= last.second) continue;
final.push_back(a[i]);
last = a[i];
}
a = final;
}
auto sq = [&](ll x) {
return 1LL * x * x;
};
a.insert(a.begin(), {0, 0});
n = a.size() - 1;
ll dp[n + 1], new_dp[n + 1];
new_dp[0] = 0;
for (int i = 0; i <= n; i++) dp[i] = 1e18;
dp[0] = 0;
for (int iter = 0; iter < k; iter++) {
CHT cht;
for (int i = 1; i <= n; i++) {
if (dp[i - 1] != 1e18) {
cht.insert(Line(-a[i].first, dp[i - 1] - sq(max(0, a[i - 1].second - a[i].first)) + sq(a[i].first)));
}
new_dp[i] = cht.query(2 * a[i].second) + sq(a[i].second);
}
for (int i = 0; i <= n; i++) dp[i] = min(dp[i], new_dp[i]);
}
return dp[n];
}
