#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;
const int C = 1e9;
struct Lichao{
struct Line{
i64 m, c;
Line(i64 m = 0, i64 c = inf) : m(m), c(c) {}
i64 operator ()(i64 x){ return m * x + c; }
};
struct Info{
Line s;
Info *lf, *rg;
Info(Line s) : s(s), lf(0), rg(0) {}
};
Info *root = new Info({0, inf});
void ins(Info *v, int l, int r, Line nw){
if ( l == r ){
if ( v -> s(l) > nw(l) ){
v -> s = nw;
}
return;
}
int m = (l + r) / 2;
if ( v -> s.m < nw.m ) swap(v -> s, nw);
if ( v -> s(m) < nw(m) ){
if ( v -> rg ){
ins(v -> rg, m + 1, r, nw);
} else v -> rg = new Info(nw);
} else{
swap(v -> s, nw);
if ( v -> lf ){
ins(v -> lf, l, m, nw);
} else v -> lf = new Info(nw);
}
}
void ins(Line nw){ ins(root, -C, C, nw); }
i64 get(Info *v, int l, int r, i64 x){
if ( l == r ){
return v -> s(x);
}
i64 m = (l + r) / 2, ret = v -> s(x);
if ( v -> lf ) chmin(ret, get(v -> lf, l, m, x));
if ( v -> rg ) chmin(ret, get(v -> rg, m + 1, r, x));
return ret;
}
i64 get(i64 x){ return get(root, -C, C, x); }
};
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];
}
}
vector <vector<i64>> dp(n + 1, vector <i64> (k + 1, inf));
vector <Lichao> lch(k + 1);
for ( int i = 0; i <= k; i++ ){
dp[0][i] = 0;
}
for ( int i = 1; i <= n; i++ ){
for ( int g = 0; g <= k; g++ ){
lch[g].ins({2LL * h[i], dp[i - 1][g - 1] + h[i] * 1LL * h[i] - q[i]});
}
for ( int g = k; g >= 0; g-- ){
dp[i][g] = lch[g].get(a[i]) + a[i] * 1LL * a[i];
}
}
return dp[n][k];
}
