#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<long long,long long> pt;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7, MAXM=1e6+7;
const ll INF=1e18+7;
pt T[LIM];
pair<pt,int>tr[4*MAXM];
ll dp[LIM], lst[LIM], n, m, k, N=2;
ll f(pt a, ll x) {
return a.st*x+a.nd;
}
void upd(pt x, int ind) {
int v=1, l=0, r=N-1;
while(true) {
int mid=(l+r)/2;
bool a=f(x, l)<f(tr[v].st, l);
bool b=f(x, mid)<f(tr[v].st, mid);
if(b) {
swap(tr[v].st, x);
swap(tr[v].nd, ind);
}
if(l==r) return;
v*=2;
if(a!=b) r=mid;
else {
++v;
l=mid+1;
}
}
}
pair<ll,int>cnt(ll x) {
int v=x+N;
pair<ll,int>ans={INF, 0};
while(v) {
ans=min(ans, {f(tr[v].st, x), tr[v].nd});
v/=2;
}
return ans;
}
int solve(ll c) {
rep(i, 2*N) tr[i]={{0, INF}, MAXM};
upd({-2*T[0].st, T[0].st*T[0].st-2*T[0].st}, -1);
rep(i, n) {
pair<ll,int>p=cnt(T[i].nd);
dp[i]=p.st+T[i].nd*T[i].nd+2*T[i].nd+1+c;
lst[i]=p.nd;
if(i<n-1) {
ll b=max(T[i].nd-T[i+1].st+1, 0ll);
b*=-b;
b+=dp[i]+T[i+1].st*T[i+1].st-2*T[i+1].st;
upd({-2*T[i+1].st, b}, i);
}
}
int akt=n-1, ans=0;
while(akt>=0) {
++ans;
akt=lst[akt];
}
return ans;
}
ll take_photos(int Z, int M, int K, vector<int>r, vector<int>c) {
pair<ll,ll>P[Z];
rep(i, Z) P[i]={min(r[i], c[i]), -max(r[i], c[i])};
sort(P, P+Z);
ll ma=-1;
rep(i, Z) {
if(-P[i].nd>ma) {
ma=-P[i].nd;
T[n]={P[i].st, -P[i].nd};
++n;
}
}
m=M; k=K;
while(N<m) N*=2;
ll po=0, ko=10000000000000;
while(po<ko) {
ll sr=(po+ko)/2;
if(solve(sr)>k) po=sr+1; else ko=sr;
}
solve(po);
return dp[n-1]-po*k;
}
