#include "aliens.h"
#include <bits/stdc++.h>
#define ll long long
#define sz size()
#define all(x) x.begin(),x.end()
#define vll vector<ll>
#define str string
#define pb push_back
#define pof pop_front()
#define pf push_front
#define pob pop_back()
#define bc back()
using namespace std;
const ll N=4e3+5;
struct Line{
ll m,b;
ll operator () (ll x){return m * x + b;}
bool ok(Line x, Line y){
ll t1 = (x.b - b);
ll b1 = (m - x.m);
ll t2 = (y.b - b);
ll b2 = (m - y.m);
return t1 * b2 >= t2 * b1;
}
};
ll sq(ll x){
return x*x;
}
long long dp[N][N];
long long take_photos(int N, int M, int K, vector<int> R, vector<int> C) {
ll i,q;
ll n=N,m=M,k=K;
vll len, nxt;
vll c, r;
for(auto i : C)c.pb(i);
for(auto i : R)r.pb(i);
{//deleting unnecessary ones
vll mx(m, m), nr;
for(i=0;i<n;i++){
if(r[i] < c[i]) swap(r[i], c[i]);
mx[r[i]] = min(mx[r[i]], c[i]);
}
for(i=m-1;i>=0;i--){
if(mx[i] > i)continue;
if(nr.empty() || mx[nr.bc] > mx[i]){
nr.pb(i);
len.pb(i-mx[i]+1);
}
}
nr.pb(-1), len.pb(-1);//changing indexation
reverse(all(nr));
reverse(all(len));
r=nr;
n=r.size()-1;
k = min(k, n);
}
c.clear();
c.pb(0);
nxt.clear();
//~ cout<<endl;
for(i=1;i<=n;i++){
nxt.pb(r[i] - len[i]);
c.pb(nxt.bc + 1);
len[i - 1] = r[i - 1] - nxt[i - 1] ;
len[i - 1] = max(len[i - 1], 0ll);
//~ cout<<r[i - 1]<<' '<<nxt[i - 1]<<endl;
//~ cout<<len[i - 1]<<endl;
}
//~ cout<<endl;
len[0]=0;
nxt.pb(r[n]);
memset(dp, 0x3f, sizeof(dp));
dp[0][1]=0;
vector<deque<Line>> ch(k+5);
//~ for(i=0;i<=k;i++)ch[i].pb({-2 * nxt[0], nxt[0] * nxt[0]});
for(i=1;i<=n;i++){
for(q=1;q<=k;q++){
auto &dq = ch[q-1];
ll x = r[i];
while(dq.sz > 1 && dq[0](x) > dq[1](x)){
dq.pof;
}
if(dq.sz){
dp[i][q] = sq(r[i]) + dq[0](x);
}
else dp[i][q] = sq(r[i] - nxt[0]);
}
for(q=1;q<=k;q++){
ll m = (-2) * nxt[i];
ll b = nxt[i] * nxt[i] - len[i] * len[i] + dp[i][q];
Line cur = {m, b};
//~ if(q == 1){
//~ cout<<i<<endl;
//~ cout<<m<<' '<<b<<endl;
//~ cout<<endl;
//~ }
auto &dq = ch[q];
while((ll) dq.sz > 1 && dq[dq.sz - 2].ok(dq.bc, cur)) dq.pob;
dq.pb(cur);
}
}
long long ans=dp[n+1][0];
for(i=0;i<=k;i++) ans=min(ans,dp[n][i]);
return ans;
}
