#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
const i64 inf = 1e15;
struct Line{
i64 m, c, k;
Line(i64 m = 0, i64 c = inf, i64 k = 0) : m(m), c(c), k(k) {}
i64 operator ()(i64 x){ return m * x + c; }
bool isOpt(Line ff, Line ss){ // ff < ss
__int128 a = c - ff.c, b = c - ss.c;
a *= (ss.m - m), b *= (ff.m - m);
if ( a < b || (a == b && ff.k <= ss.k ) ){
return true;
}
return false;
}
};
long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> C) {
vector <int> a, f;
{ // deleting unnecessary ones
vector <int> g(m, m);
for ( int i = 0; i < n; i++ ){
int x = max(R[i], C[i]);
chmin(g[x], min(R[i], C[i]));
}
vector <int> nxt;
for ( int i = m - 1; i >= 0; i-- ){
g[i] = i - g[i] + 1;
if ( g[i] <= 0 ) continue;
if ( nxt.empty() || nxt.back() - g[nxt.back()] > i - g[i] ){
nxt.pb(i); f.pb(g[i]);
}
}
nxt.pb(-1), f.pb(-1); // random stuff
reverse(all(nxt));
reverse(all(f));
swap(a, nxt);
n = (int)a.size() - 1;
}
vector <i64> h(n + 1), q(n + 1);
for ( int i = 1; i <= n; i++ ){
h[i] = -a[i] + f[i];
if ( i > 1 ){
q[i] = a[i - 1] + h[i];
chmax(q[i], 0);
q[i] *= q[i];
}
}
i64 tmp = 0;
auto opt = [&](i64 lm){
vector <i64> dp(n + 1, inf), fa(n + 1);
dp[0] = 0;
deque <Line> dq;
for ( int i = 1; i <= n; i++ ){
Line cur = {2LL * h[i], dp[i - 1] + h[i] * 1LL * h[i] - q[i] + lm, fa[i - 1] + 1};
while ( dq.size() > 1 && dq[(int)dq.size() - 2].isOpt(cur, dq.back()) ){
dq.pop_back();
} dq.pb(cur);
while ( dq.size() > 1 && (dq[0](a[i]) > dq[1](a[i]) || (dq[0](a[i]) == dq[1](a[i]) && dq[0].k >= dq[1].k)) ){
dq.pop_front();
}
dp[i] = dq[0](a[i]) + a[i] * 1LL * a[i];
fa[i] = dq[0].k;
}
tmp = dp.back();
return fa.back();
};
// opt(i - 1) >= opt(i)
i64 l = 0, r = inf;
while ( l < r ){
i64 m = (l + r) / 2;
if ( opt(m) <= k ){
r = m;
} else l = m + 1;
} opt(r);
return tmp - r * k;
}
