#include "aliens.h"
#include <bits/stdc++.h>
#define ll long long
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
bool Q ;
struct Line {
mutable ll m, p, k;
bool operator<(const Line& o) const {
return Q ? k < o.k : m < o.m;
}
};
struct LineContainer : multiset<Line> {
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
const ll inf = LLONG_MAX;
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b);
}
bool isect(iterator x, iterator y) {
if (y == end()) {
x->k = inf;
return false;
}
if (x->m == y->m)
x->k = x->p > y->p ? inf : -inf;
else
x->k = div(y->p - x->p, x->m - y->m);
return x->k >= y->k;
}
void add(ll m, ll p) {
auto z = insert({m, p, 0}), y = z++, x = y;
while (isect(y, z))
z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->k >= y->k)
isect(x, erase(y));
}
ll query(ll x) {
if(empty())
return -MX;
assert(!empty());
Q = 1; auto l = *lower_bound({0,0,x}); Q = 0;
return l.m * x + l.p;
}
}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);
}
memset(dp,61,sizeof(dp));
k = min(k,n);
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];
}
