#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
namespace NSolver {
template <typename TLookupType>
void ImplementSMAWK(TLookupType lookup,
const std::vector<size_t>& rows,
const std::vector<size_t>& columns,
std::vector<size_t>& result) {
if (rows.empty()) {
return;
}
/// REDUCE
std::vector<size_t> survivingColumns;
for (size_t column: columns) {
while (true) {
if (survivingColumns.empty()) {
break;
}
size_t row = rows[survivingColumns.size() - 1];
const auto& firstValue = lookup(row, column);
const auto& secondValue = lookup(row, survivingColumns.back());
if (!firstValue.has_value() || (secondValue.has_value() && *firstValue >= *secondValue)) {
break;
}
survivingColumns.pop_back();
}
if (survivingColumns.size() < rows.size()) {
survivingColumns.push_back(column);
}
}
std::vector<size_t> oddRows;
for (size_t i = 1; i < rows.size(); i += 2) {
oddRows.push_back(rows[i]);
}
ImplementSMAWK(lookup, oddRows, columns, result);
std::unordered_map<size_t, size_t> columnIndices;
for (size_t i = 0; i != survivingColumns.size(); ++i) {
columnIndices[survivingColumns[i]] = i;
}
/// INTERPOLATE
size_t start = 0;
for (size_t r = 0; r < rows.size(); r += 2) {
size_t row = rows[r];
size_t stop = survivingColumns.size() - 1;
size_t argmin = survivingColumns[start];
auto minimum = lookup(row, argmin);
if (r + 1 < rows.size()) {
stop = columnIndices[result[rows[r + 1]]];
}
for (size_t column = start + 1; column <= stop; ++column) {
auto val = lookup(row, survivingColumns[column]);
if (column == start || (val.has_value() && (!minimum.has_value() || *val < *minimum))) {
argmin = survivingColumns[column];
minimum = val.value();
}
}
result[row] = argmin;
start = stop;
}
}
template<typename TLookupType>
std::vector<size_t> SMAWK(int n, int m, TLookupType lookup, bool transpose = false) {
std::vector<size_t> rows(n);
std::vector<size_t> columns(m);
std::iota(rows.begin(), rows.end(), 0);
std::iota(columns.begin(), columns.end(), 0);
if (transpose) {
std::swap(rows, columns);
}
std::vector<size_t> result(rows.size());
auto lookupTranspose = [&](size_t i, size_t j) {
return transpose ? lookup(j, i) : lookup(i, j);
};
ImplementSMAWK(lookupTranspose, rows, columns, result);
return result;
}
const long long INF = 1ll << 35;
using ll = long long;
template <typename TPenaltyFunct, typename TConvertFunction, typename T = ll>
std::vector<std::pair<size_t, T>> Solve(size_t n, TPenaltyFunct penalty, T init, TConvertFunction convert, bool debug = false) {
size_t r = 0;
std::vector<std::pair<size_t, std::optional<T>>> N(n + 1); // 1 indexation
std::vector<std::pair<size_t, std::optional<T>>> E(n + 1), D(n + 1);
D[0] = {0, init};
E[0] = {0, convert(init)};
auto B = [&](size_t i, size_t j) {
if (!D[i].second.has_value()) {
D[i] = {E[i].first, convert(E[i].second.value())};
}
return D[i].second.value() + penalty(i, j);
};
for (size_t c = 1; c <= n;) {
assert(r < c);
size_t p = std::min(2 * c - r, n);
size_t gRows = c - r + 1;
size_t gCols = p - c + 1;
auto GLookup = [&](int i, int j) {
if (i == 0) return N[c + j].second;
else return std::optional<T>(B(r - 1 + i, c + j));
};
auto GLookupIndex = [&](int i, int j) {
if (i == 0) return N[c + j].first;
else return size_t(r - 1 + i);
};
const std::vector<size_t> F = SMAWK(gRows, gCols, GLookup, true);
if (debug) {
std::cerr << "Matrix G: [" << std::endl;
for (size_t i = 0; i < gRows; ++i) {
for (size_t j = 0; j < gCols; ++j) {
std::cerr << "\t\t" << GLookup(i, j).value_or(-100) << "\t";
}
std::cerr << std::endl;
}
std::cerr << "]" << std::endl;
std::cerr << "column minima = [ ";
for (size_t i = 0; i < gCols; ++i) {
std::cerr << F[i];
if (i + 1 < gCols) {
std::cerr << ", ";
}
}
std::cerr << " ];" << std::endl;
}
E[c] = std::make_pair(GLookupIndex(F[0], 0), GLookup(F[0], 0));
D[c] = std::make_pair(E[c].first, convert(E[c].second));
size_t j = c + 1;
for (; j <= p; ++j) {
T val = B(j - 1, j);
if (val < GLookup(F[j - c], j - c)) {
E[j] = std::make_pair(j - 1, std::optional<T>(val));
D[j] = std::make_pair(E[j].first, convert(E[j].second));
break;
} else {
E[j] = std::make_pair(GLookupIndex(F[j - c], j - c), GLookup(F[j - c], j - c));
D[j] = std::make_pair(E[j].first, convert(E[j].second));
if (B(j - 1, p) < GLookup(F[p - c], p - c)) {
for (size_t tmp = j + 1; tmp <= p; ++tmp) {
N[tmp] = std::make_pair(GLookupIndex(F[tmp - c], tmp - c), GLookup(F[tmp - c], tmp - c));
}
break;
}
}
}
if (j <= p) {
c = j + 1;
r = j - 1;
} else {
r = std::max(r, r - 1 + F[p - c]);
c = p + 1;
}
}
std::vector<std::pair<size_t, T>> result(n + 1);
for (size_t i = 0; i <= n; ++i) {
result[i] = {D[i].first, D[i].second.value()};
}
return result;
}
}
namespace Solver {
const int N = 1e5 + 5;
std::pair<int, int> input[N];
int l[N], r[N];
int n, m, k;
ll dp[N];
int trace[N];
void process() {
std::sort(input, input + n, [](const auto& x, const auto& y) {
return x.first < y.first || (x.first == y.first && x.second > y.second);
});
int rmax = -1;
int cnt = 0;
for (int i = 0; i != n; ++i) {
if (rmax < input[i].second) {
rmax = input[i].second;
++cnt;
l[cnt] = input[i].first;
r[cnt] = input[i].second;
}
}
n = cnt;
}
ll sqr(ll a, bool check = false) {
return check ? sqr(std::max(a, 0ll)) : a * 1ll * a;
}
std::pair<size_t, ll> check(ll lambda) {
auto penalty = [&](int i, int j) {
return lambda +
sqr(r[j] - l[i + 1]) -
sqr(r[i] - l[i + 1], true);
};
auto convert = [&](std::optional<long long> x) {
return x;
};
auto result = NSolver::Solve(n, penalty, 0ll, convert, false);
/*std::cerr << "lambda v2 = " << lambda << std::endl;
for (int i = 0; i <= n; ++i) {
std::cerr << "{" << result[i].first << ", " << result[i].second << "} ";
}
std::cerr << std::endl;*/
int layersCount = 0;
for (size_t i = n; i != 0; i = result[i].first) {
++layersCount;
}
return {layersCount, result[n].second};
}
ll solve() {
process();
ll l = 0;
ll r = m * 1ll * m;
while(l < r) {
ll mid = ((l + r) >> 1);
if (check(mid).first <= k) {
r = mid;
} else {
l = mid + 1;
}
}
return check(l).second - l * k;
}
};
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
Solver::n = n;
Solver::m = m;
Solver::k = k;
for (int i = 0; i < n; ++i) {
if (r[i] > c[i]) {
std::swap(r[i], c[i]);
}
Solver::input[i].first = r[i];
Solver::input[i].second = ++c[i];
}
return Solver::solve();
}
