#include "aliens.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf = 5e4+9,K = 509,MX = 1e18+9;
ll sqr(ll x){
return x*x;
}
ll dp[K][inf];
pair<ll,ll> a[inf];
vector<pair<ll,ll> > all;
bool cmp(pair<ll,ll> x,pair<ll,ll> y){
if(x.first == y.first)
return x.second > y.second;
return x.first < y.first;
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
for(int i=0;i<n;i++)
r[i]++,c[i]++,
all.push_back( make_pair(min(r[i],c[i]),max(r[i],c[i])) );
sort(all.begin(),all.end());
n = 1;
a[n] = all[0];
for(auto o:all){
if(o.second <= a[n].second)
continue;
a[++n] = make_pair(o.first,-o.second);
}
memset(dp,61,sizeof(dp));
dp[0][0] = 0;
for(ll j=1;j<=k;j++){
for(ll i=1;i<=n;i++){
dp[j][i] = dp[j-1][i];
for(ll z = 1;z<=i;z++)
dp[j][i] = min(dp[j][i] ,
dp[j-1][z-1] + sqr(a[i].second - a[z].first+1) -
sqr(max(0ll,a[z-1].second - a[z].first+1)) );
}
}
return dp[k][n];
}
