#include "aliens.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const ll inf = 1e5+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;
}
// this code to get maximum
// to get minimum use -m , -p , -query
struct line{
ll m,p;
ll eval(ll x){
return m*x+p;
}
ld intersectX(line l){
return (ld) (p - l.p) / (l.m - m);
}
};
struct LineContainer {
deque<line> dq;
#define last dq.size()-1
void add(ll m,ll p){
line cur = {m,p};
while(dq.size() >= 2 && dq[last-1].intersectX(cur) <= dq[last-1].intersectX(dq[last]))
dq.pop_back();
dq.push_back(cur);
}
ll query(ll x){
while(dq.size() >= 2 && dq[0].eval(x) <= dq[1].eval(x))
dq.pop_front();
return dq[0].eval(x);
}
}lc;
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
for(ll 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(),cmp);
n = 1;
a[1] = all[0];
for(auto o:all){
if(o.second <= a[n].second)
continue;
a[++n] = make_pair(o.first,o.second);
}
k = min(k,n);
ll dp[k+2][n+2] = {0};
memset(dp,61,sizeof(dp));
dp[0][0] = 0;
for(ll j=1;j<=k;j++){
for(ll i=1;i<=n;i++){
ll m = -2ll * a[i].first ,
p = sqr(a[i].first) + dp[j-1][i-1] - sqr(max(0ll,a[i-1].second - a[i].first+1) ) - 2ll*a[i].first;
lc.add(-m,-p);
ll add = sqr(a[i].second) + 2ll*a[i].second + 1 , x = a[i].second;
dp[j][i] = add - lc.query(x);
/*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];
}
