#include <bits/stdc++.h>
#include "aliens.h"
#define ll long long
using namespace std;
constexpr static ll INF = 1e15;
vector<array<int, 2>> get_cells(const vector<int>& r, const vector<int>& c) {
const int n = r.size();
vector<array<int, 2>> cells;
for (int i = 0; i < n; i++) {
cells.push_back({min(r[i], c[i]), -max(r[i], c[i])});
}
sort(cells.begin(), cells.end());
vector<array<int, 2>> final_cells;
int lastc = -1;
for (auto [r, c] : cells) {
if (-c <= lastc)
continue;
lastc = -c;
final_cells.push_back({r, -c});
}
return final_cells;
}
ll calculate_cost(array<ll, 2> line, ll c) {
return line[0] + line[1] * c + c * c;
}
bool beating_intercept(const deque<array<ll, 2>>& d, ll y2, ll s2) {
if (d.size() == 0) return false;
if (y2 < d[0][0]) return true;
if (d.size() == 1) return false;
auto [ y1, s1 ] = d.back();
auto [ y0, s0 ] = d[d.size()-2];
assert(y0 <= y1 && y1 <= y2);
assert(s2 <= s1 && s1 <= s0);
return (y1 - y2) * (s1 - s0) >= (y0 - y1) * (s2 - s1);
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
assert(n*k <= 1e8);
vector<array<int, 2>> cells = get_cells(r, c);
n = cells.size();
//cout << n << "\n";
/*
for (auto [r, c] : cells) {
cout << r << " " << c << "\n";
}
*/
// cout << k << "\n";
//vector<vector<ll>> dp(n+1, vector<ll>(k+1, INF));
vector<deque<array<ll, 2>>> dp(k+1); // (Initial point, slope)
for (int i = 0; i <= k; i++) {
ll y_intercept = static_cast<ll>(cells[0][0] - 1) * (cells[0][0] - 1);
ll slope = - 2 * (cells[0][0] - 1);
dp[i].push_back({y_intercept, slope});
//cout << i << " " << 0 << ": " << y_intercept << " + " << slope << "x\n";
}
for (int j = 1; j <= k; j++) {
for (int i = 1; i <= n; i++) {
auto [r, c] = cells[i-1];
while (dp[j-1].size() > 1 && calculate_cost(dp[j-1][0], c) > calculate_cost(dp[j-1][1], c)) dp[j-1].pop_front();
ll cost = calculate_cost(dp[j-1][0], c);
if (i < n) {
ll y_intercept = cost + static_cast<ll>(cells[i][0] - 1) * (cells[i][0] - 1) - max<ll>(0, c - cells[i][0] + 1) * max<ll>(0, c - cells[i][0] + 1);
ll slope = - 2 * (cells[i][0] - 1);
while (beating_intercept(dp[j], y_intercept, slope)) dp[j].pop_back();
dp[j].push_back({y_intercept, slope});
//cout << j << " " << i << ": " << y_intercept << " + " << slope << "x\n";
}
if (i == n && j == k) {
return cost;
}
}
}
assert(false);
}
