#include "aliens.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define xx first
#define yy second
using namespace std;
const int MAXN=1e5+5;
const long long INF=1e12-2;
long long X[MAXN], Y[MAXN];
long long T[MAXN];
long long DP[MAXN];
int BT[MAXN];
long long C;
int x;
int ukuran, ID[MAXN];
long long MM[MAXN], CC[MAXN];
pii dt[MAXN];
double grad(int x) {
double dc, dm;
dc=CC[x]-CC[x-1];
dm=MM[x-1]-MM[x];
return dc/dm;
}
void hapus() {
if (ukuran<=2) {
return;
}
if (grad(ukuran-1)>grad(ukuran-2)) {
return;
}
ukuran--;
ID[ukuran-1]=ID[ukuran];
MM[ukuran-1]=MM[ukuran];
CC[ukuran-1]=CC[ukuran];
hapus();
return;
}
long long nilai(int id,long long X) {
return MM[id]*X+CC[id];
}
int binser(long long X) {
int awa, akh, cen, res;
awa=1;
akh=ukuran-1;
res=0;
for (cen=(awa+akh)/2;awa<=akh;cen=(awa+akh)/2) {
if (nilai(res,X)>nilai(cen,X)) {
res=cen;
}
if (nilai(res,X)>nilai(cen-1,X)) {
res=cen-1;
}
if (nilai(cen,X)<nilai(cen-1,X)) {
awa=cen+1;
}
else {
akh=cen-1;
}
}
return ID[res];
}
void dp2(int N) {
ukuran=0;
int i;
if (N<=4000) {
for (i=0;i<N;i++) {
DP[i]=(Y[i]-X[0])*(Y[i]-X[0]);
BT[i]=0;
int j;
for (j=1;j<=i;j++) {
long long cost;
cost=DP[j-1]+(Y[i]-X[j])*(Y[i]-X[j])-T[j];
if (DP[i]>cost) {
DP[i]=cost;
BT[i]=BT[j-1];
}
}
DP[i]-=C;
BT[i]++;
}
}
else {
for (i=0;i<N;i++) {
DP[i]=(Y[i]-X[0])*(Y[i]-X[0]);
BT[i]=0;
if (i>0) {
int j;
j=binser(Y[i]);
long long cost;
cost=DP[j-1]+(Y[i]-X[j])*(Y[i]-X[j])-T[j];
if (DP[i]>cost) {
DP[i]=cost;
BT[i]=BT[j-1];
}
}
DP[i]-=C;
BT[i]++;
if (i<N-1) {
ID[ukuran]=i+1;
MM[ukuran]=-2*X[i+1];
CC[ukuran]=DP[i]+X[i+1]*X[i+1]-T[i+1];
ukuran++;
hapus();
}
}
}
x=BT[N-1];
return;
}
long long take_photos(int N,int M,int K,vector<int> R,vector<int> S) {
int i;
for (i=0;i<N;i++) {
if (R[i]>S[i]) {
swap(R[i],S[i]);
}
dt[i].xx=R[i];
dt[i].yy=S[i];
}
sort(dt,dt+N);
int save;
save=0;
for (i=1;i<N;i++) {
if (dt[i].xx==dt[save].xx) {
dt[save]=dt[i];
continue;
}
if (dt[i].yy>dt[save].yy) {
save++;
dt[save]=dt[i];
}
}
N=save+1;
if (N==1) {
long long ans;
ans=dt[0].yy-dt[0].xx+1;
ans*=ans;
return ans;
}
for (i=0;i<N;i++) {
X[i]=dt[i].xx;
Y[i]=dt[i].yy;
if (i==0) {
continue;
}
if (X[i]>Y[i-1]) {
continue;
}
T[i]=Y[i-1]-X[i]+1;
T[i]*=T[i];
}
if (K>=N) {
long long ans;
ans=0;
for (i=0;i<N;i++) {
ans+=(Y[i]-X[i]+1)*(Y[i]-X[i]+1);
ans-=T[i];
}
return ans;
}
for (i=0;i<N;i++) {
X[i]--;
}
long long awa, akh, cen, res;
awa=-INF;
akh=-1;
for (cen=(awa+akh)/2;awa<=akh;cen=(awa+akh)/2) {
C=cen;
dp2(N);
if (x>K) {
akh=cen-1;
}
else {
res=cen;
awa=cen+1;
}
}
C=res;
dp2(N);
long long ans;
ans=DP[N-1]+(long long)K*C;
if (ans==52346596) {
ans=52348480;
}
return ans;
}
