#include "aliens.h"
#include <bits/stdc++.h>
#warning fa cu ll
using namespace std;
using ll = long long;
#define int ll
#define sz(x) (int)(x).size()
const int nmax = 1e6 + 5;
struct line {
int chosen = 0;
ll dp = 0, b = (ll)nmax * nmax;
line(int x = 0, ll y = (ll)nmax * nmax, ll z = (ll)nmax * nmax): chosen(x), dp(y), b(z) {;}
ll operator()(const ll& x) const { return b * x + dp; }
bool operator()(const line& form, const line& cand) const {
return (dp - form.dp) * (cand.b - b) > (dp - cand.dp) * (form.b - b) || ((dp - form.dp) * (cand.b - b) == (dp - cand.dp) * (form.b - b) && (b < cand.b || (b == cand.b && dp < cand.dp)));
}
};
struct CHT {
line cht[nmax];
int ptr, lim;
struct undo_info {
line last;
int ptrlast;
int lstptr;
int lstlim;
undo_info(line a, int x, int y, int z): last(a), ptrlast(x), lstptr(y), lstlim(z) {;}
};
vector<undo_info> undost;
int getT() { return sz(undost); }
void push(line nv) {
undost.emplace_back(line(), 0, ptr, lim);
while(lim > 1 && nv(cht[lim - 2], cht[lim - 1])) lim--;
undost.back().last = cht[lim];
undost.back().ptrlast = lim;
cht[lim++] = nv;
ptr = min(lim - 1, ptr);
}
void undo() {
cht[undost.back().ptrlast] = undost.back().last;
ptr = undost.back().lstptr;
lim = undost.back().lstlim;
undost.pop_back();
//cerr << "? " << lim << '\n';
}
void undo(int T) {
assert(T >= 0);
while(getT() > T)
undo();
}
line query(int x) { // blea??
while(ptr < lim - 1 && cht[ptr + 1](x) < cht[ptr](x))
ptr++;
//cerr << x << ' ' << cht[ptr](x) << '\t';
//for(int i = 0; i < lim; i++)
//cerr << cht[i](x) << ' ';
//cerr << '\n';
return cht[ptr];
}
void init() {
undost.clear();
ptr = 0;
lim = 1;
cht[0] = line(0, 0, 0);
undost.reserve(nmax);
}
} cht;
ll p2(ll x) { return x * x; }
line calculate(const vector<int>& height, ll C) {
cht.init();
vector<ll> dp(sz(height));
vector<int> chosen(sz(height)), altern = height, st;
st.reserve(sz(height));
st.emplace_back(0);
for(int i = 1; i < sz(altern); i++) altern[i] -= i;
//for(auto x : height)
//cerr << x << ' ';
//cerr << '\n';
//for(auto x : altern)
//cerr << x << ' ';
//cerr << '\n';
for(int i = 1; i < sz(height); i++) {
while(altern[st.back()] < altern[i])
(height[st.back()]? cht.undo() : void()),
st.pop_back();
if(height[i] != 0) {
cht.push(line(chosen[st.back()], (ll)dp[st.back()] - p2(st.back()) - (ll)2 * st.back() * (altern[i]), (ll)2 * (altern[i])));
auto best = cht.query(i);
dp[i] = best(i) + p2(i) + C;
chosen[i] = best.chosen + 1;
}
else {
chosen[i] = chosen[i - 1], dp[i] = dp[i - 1];
}
//cerr << dp[i] << ' ';
st.push_back(i);
//for(auto x : st) cerr << x << ' ';
//cerr << "\n---\n";
//cerr << dp[i] << '\n';
}
//cerr << '\n';
return line{chosen.back(), dp.back(), 0};
}
ll smenufromaliens(const vector<int>& height, int k) {
ll lim = -1;
for(ll i = (1LL << 40); i > 0; i >>= 1) {
if(calculate(height, lim + i).chosen > k)
lim += i;
}
return lim + 1;
}
ll take_photos(signed n, signed m, signed k, std::vector<signed> r, std::vector<signed> c) {
if(n == 0) return 0;
vector<int> height(m + 1);
height[0] = m + 5;
for(int i = 0; i < n; i++)
r[i]++,
c[i]++,
height[max(r[i], c[i])] = max(height[max(r[i], c[i])], (ll)abs(r[i] - c[i]) + 1);
while(height.back() == 0)
height.pop_back();
int lim = smenufromaliens(height, k);
//int lim = 0;
auto lol = calculate(height, lim);
//cerr << lim << ' ' << lol.dp << ' ' << lol.chosen << ' ' << k << '\n';
return (ll)lol.dp - (ll)lim * k;
}
#undef int
