#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
int n;
pii ans;
vector<int> r, c;
struct line{
int m, c, id;
line (int m, int c, int id): m(m), c(c), id(id){}
int operator()(int x){return m*x+c;}
};
deque <line> cht;
pii query(int x){
while (cht.size()>1){
if (cht[0](x)>cht[1](x))cht.pop_front();
else break;
}
return mp(cht[0](x), cht[0].id);
}
long double intersect(line a, line b){
return (long double)(b.c-a.c)/(a.m-b.m);
}
void insert(int m, int c, int id){
line l = line(m, c, id);
while (!cht.empty()&&cht.back().m==m){
if (cht.back().c>c)cht.pop_back();
else return;
}
while (cht.size()>1){
int s = cht.size();
if (intersect(cht[s-1], l)<=intersect(cht[s-2], l))cht.pop_back();
else break;
}
cht.push_back(l);
}
bool custom(pii a, pii b){
if (a.first==b.first)return a.second>b.second;
return a.first<b.first;
}
int sq(int a){
return a*a;
}
void alien(int pen){
cht.clear();
vector<pii> dp(n+1, mp(LLONG_MAX/2, LLONG_MAX/2));
dp[0]=mp(0, 0);
for (int i=1; i<=n; ++i){
insert(-2*r[i], dp[i-1].first+sq(r[i])-2*r[i]-sq(max(0ll, c[i-1]-r[i]+1)), dp[i-1].second);
pii res = query(c[i]);
dp[i]=mp(res.first+sq(c[i])+2*c[i]+pen+1, res.second+1);
}
ans=dp[n];
}
long long take_photos(signed _n, signed m, signed k, vector<signed> _r, vector<signed> _c){
vector<pii> temp(_n), vect;
for (int i=0; i<_n; ++i)temp[i]=mp(min(_r[i], _c[i]), max(_c[i], _r[i]));
sort(temp.begin(), temp.end(), custom);
vect.pb(mp(-1, -1));
for (int i=0; i<_n; ++i)if (vect.back().second<temp[i].second)vect.pb(temp[i]);
n=vect.size()-1;
r.resize(n+1);
c.resize(n+1);
for (int i=0; i<=n; ++i)r[i]=vect[i].first, c[i]=vect[i].second;
int low=-1, high=LLONG_MAX/2;
while (low+1<high){
int mid=(low+high)/2;
alien(mid);
if (ans.second<=k)high=mid;
else low=mid;
}
alien(high);
return ans.first-k*high;
}
