#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#define vec vector
#define int long long
const int INF = 1e18;
int eval(pair<int, int> f, int x) {
return f.first * x + f.second;
}
// returns true iff f(intersect(g, h)) < g(intersect(g, h))
bool comp_mid(pair<int, int> f, pair<int, int> g, pair<int, int> h) {
auto [a1, b1] = f; auto [a2, b2] = g; auto [a3, b3] = h;
return (a1-a2)*(b3-b2) < (a3 - a2)*(b1-b2);
}
int take_photos(int32_t n, int32_t m, int32_t k, std::vector<int32_t> r, std::vector<int32_t> c) {
vec<pair<int, int>> init_rang(n);
for(int i = 0; i<n; i++) {
init_rang[i].first = min(r[i], c[i]);
init_rang[i].second = max(r[i], c[i]);
}
sort(init_rang.begin(), init_rang.end());
vec<pair<int, int>> rang{init_rang[0]};
for(int i = 1; i<n; i++) {
if(init_rang[i].second <= rang.back().second) continue;
if(init_rang[i].first == rang.back().first) {
rang.back().second = init_rang[i].second;
}
else {
rang.push_back(init_rang[i]);
}
}
n = rang.size();
vec<vec<int>> dp(n+1, vec<int>(k+1, INF));
for(int i = 0; i<=k; i++) dp[n][i] = 0;
vec<deque<pair<int, int>>> cts(k+1);
for(int i = 0; i<n; i++) {
rang[i].second++;
}
// calls to here should have parameter x decreasing for any given i
auto query = [&](int i, int x) {
while(cts[i].size() >= 2 && eval(cts[i][cts[i].size()-2], x) < eval(cts[i].back(), x)) {
cts[i].pop_back();
}
return eval(cts[i].back(), x);
};
// calls to here should have parameter a increasing for any given i
auto insert = [&](int i, int a, int b) {
while(cts[i].size() >= 2 && comp_mid({a, b}, cts[i][0], cts[i][1])) cts[i].pop_front();
cts[i].push_front({a, b});
};
for(int i = n-1; i>=0; i--) {
for(int j = 1; j<=k; j++) {
// insert a line a = -2r[i] b = r[i]**2 + dp[i+1][j-1]
insert(j, -2*rang[i].second, pow(rang[i].second, 2) + dp[i+1][j-1]);
}
for(int j = 1; j<=k; j++) {
int mn = query(j, rang[i].first); // minimum value at position l[i] of lines in ct[j]
dp[i][j] = (i>0 & (rang[i-1].second > rang[i].first) ? (-pow(rang[i-1].second - rang[i].first, 2)) : 0) + pow(rang[i].first, 2) + mn;
}
}
int ans = INF;
for(int i = 0; i<=k; i++) {
ans = min(ans, dp[0][i]);
}
return ans;
}
