#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()
struct cht {
vector<pl> stk;
vi cnt;
int pt=0;
void add(ll a, ll b, int c) {
while (stk.size()>1 && (1.0*stk[stk.size()-2].se-b)/(a-stk[stk.size()-2].fi) <= (1.0*stk.back().se-stk[stk.size()-2].se)/(stk[stk.size()-2].fi-stk.back().fi)) {
stk.pop_back();
cnt.pop_back();
}
stk.pb({a,b});
cnt.pb(c);
if (pt>=stk.size()) {
pt=stk.size()-1;
}
}
pl get(ll x) {
while (pt<stk.size()-1 && ((__int128_t)(x)*stk[pt].fi+stk[pt].se)>=((__int128_t)(x)*stk[pt+1].fi+stk[pt+1].se)) {
pt++;
}
return {x*stk[pt].fi+stk[pt].se,cnt[pt]};
}
};
vector<pl> po;
pl solve(int n, int k, ll p) {
cht chts;
chts.add(2*(1-po[0].fi),(1-po[0].fi)*(1-po[0].fi),0);
vl dp(n+1,2e12);
vl cnt(n+1,0);
dp[0]=0;
for (int i=1; i<=n; i++) {
dp[i]=po[i-1].se*po[i-1].se+chts.get(po[i-1].se).fi+p;
cnt[i]=chts.get(po[i-1].se).se+1;
ll sub=0;
if (i!=n && po[i-1].se>=po[i].fi) {
sub=(po[i-1].se-po[i].fi+1)*(po[i-1].se-po[i].fi+1);
}
if (i!=n) {
chts.add(2*(1-po[i].fi),dp[i]-sub+(1-po[i].fi)*(1-po[i].fi),cnt[i]);
}
}
return {dp[n]-cnt[n]*p,cnt[n]};
/*vector<cht> chts(k+1);
for (int i=0; i<k; i++) {
chts[i].add(2*(1-po[0].fi),(1-po[0].fi)*(1-po[0].fi));
}
vector<vl> dp(n+1,vl(k+1,2e12));
dp[0][0]=0;
for (int i=1; i<=n; i++) {
for (int j=k; j>=1; j--) {
dp[i][j]=min(dp[i][j],po[i-1].se*po[i-1].se+chts[j-1].get(po[i-1].se));
ll sub=0;
if (i!=n && po[i-1].se>=po[i].fi) {
sub=(po[i-1].se-po[i].fi+1)*(po[i-1].se-po[i].fi+1);
}
if (i!=n) {
chts[j].add(2*(1-po[i].fi),dp[i][j]-sub+(1-po[i].fi)*(1-po[i].fi));
}
}
}
return *min_element(all(dp[n]));*/
}
ll take_photos(int n, int m, int k, vi r, vi c) {
vector<pl> tpo(n);
vl pmx(n);
for (int i=0; i<n; i++) {
tpo[i].fi=min(r[i],c[i]);
tpo[i].se=max(r[i],c[i]);
}
sort(all(tpo));
po.pb(tpo[0]);
for (int i=0; i<n; i++) {
if (po.back().fi==tpo[i].fi) {
po.back().se=tpo[i].se;
}
else if (po.back().se<tpo[i].se) {
po.pb(tpo[i]);
}
}
n=po.size();
k=min(n,k);
ll tl=0,tr=1ll*m*m;
ll ans=2e12;
while (tl<=tr) {
ll m=tl+(tr-tl)/2;
pl s=solve(n,k,m);
if (s.se>k) {
tl=m+1;
}
else {
ans=min(ans,s.fi);
tr=m-1;
}
}
return ans;
}
