#include "aliens.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=51100;
const ll maxk=110;
const ll inf=1e9+900;
ll tav2(ll x){
return x*x;
}
ll mx[maxn];
ll dp[maxn][maxk];
ll findMn(ll l,ll r){
ll ans=inf;
for(ll i=l;i<=r;i++){
ans=min(ans,mx[i]);
}
return ans;
}
ll cost(ll i,ll x){
// cout<<i<<' '<<x<<"*";
ll t=findMn(x+1,i);
// cout<<t<<"^";
if(findMn(i-t,x)>i-t){
// cout<<"#"<<tav2(i-t+1)<<endl;;
return tav2(i-t+1);
}
if(t>=x){
// cout<<tav2(i-t+1)<<endl;
return tav2(i-t+1);
}
// cout<<tav2(i-t+1)-tav2(x-t+1)<<endl;
return tav2(i-t+1)-tav2(x-t+1);
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
swap(n,m);
fill(mx,mx+maxn,inf);
for(ll i=0;i<m;i++){
if(c[i]>r[i]){
swap(c[i],r[i]);
}
mx[r[i]]=min(mx[r[i]],(ll)c[i]);
}
for(ll i=1;i<=n;i++){
for(ll j=0;j<=k;j++){
if(mx[i-1]==inf){
dp[i][j]=dp[i-1][j];
}else{
if(j==0){
dp[i][j]=inf;
}else{
dp[i][j]=inf;
for(ll x=i-1;x>=0;x--){
dp[i][j]=min(dp[i][j],dp[x][j-1]+cost(i-1,x-1));
}
}
}
// cout<<i<<' '<<j<<":"<<dp[i][j]<<endl;
}
}
return dp[n][k];
}
