#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define double long double
#define F first
#define S second
#define ll long long
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
const ll inf=1e15;
const int MAXN=505;
typedef pair<ll,ll> pii;
ll sq(ll x){
return x*x;
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
vector<pii> ord;
fall(i,0,n-1){
if(c[i]<r[i]) swap(r[i],c[i]);
ord.pb({r[i],-c[i]});
}
sort(all(ord));
vector<pii> v;
int mx=-1;
for(auto [u,j]:ord){
j=-j;
if(mx>=j) continue;
mx=j;
v.pb({u,j});
}
n=sz(v);
vector<vector<ll>> dp(n+1,vector<ll>(k+1));
fall(i,0,n)
fall(j,0,k) dp[i][j]=inf;
dp[0][0]=0;
deque<pii> cht;
auto inter=[&](int a,int b,int c,int d){
double ret=(1.00*b-1.00*d)/(1.00*c-1.00*a);
return ret;
};
auto insert=[&](int a,int b){
while(sz(cht)>1){
auto [c,d]=cht.back(); cht.pop_back();
auto [e,f]=cht.back();
if(inter(a,b,c,d)>inter(c,d,e,f)){
cht.pb({c,d});
break;
}
}
cht.pb({a,b});
return;
};
fall(j,1,k){
cht.clear();
cht.pb({-2*v[0].F,sq(v[0].F)}); //a frente tem os maiores coeficientes a's
fall(i,1,n){
while(sz(cht)>1){
auto [a,b]=cht.front(); cht.pop_front();
auto [c,d]=cht.front();
if(a*(1+v[i-1].S)+b<c*(1+v[i-1].S)+d){
cht.push_front({a,b});
break;
}
}
auto [a,b]=cht.front();
dp[i][j]=min(dp[i][j-1],a*(1+v[i-1].S)+b+sq(v[i-1].S+1));
if(i!=n && dp[i][j-1]!=inf){
insert(-2*v[i].F,dp[i][j-1]+sq(v[i].F)-sq(max(0ll,v[i-1].S-v[i].F+1)));
}
//cout<<i<<" "<<j<<" "<<dp[i][j]<<"\n";
}
}
return dp[n][k];
}
