#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
struct Dreapta {
long long factor , termen;
Dreapta (long long __factor = 0 , long long __termen = 1e18) : factor(__factor) , termen(__termen) { }
long long operator ()(long long punct) { return factor * punct + termen; }
};
static pair <Dreapta , int> arbore[2000000];
static vector < pair <int , int> > coordonate;
void Insert (const int nod , const int stanga , const int dreapta , pair <Dreapta , int> candidat)
{
if (stanga == dreapta)
{ return; }
const int mijloc = (stanga + dreapta) >> 1;
const bool factor_1 = (make_pair(candidat.first(stanga) , candidat.second) < make_pair(arbore[nod].first(stanga) , arbore[nod].second));
const bool factor_2 = (make_pair(candidat.first(mijloc) , candidat.second) < make_pair(arbore[nod].first(mijloc) , arbore[nod].second));
if (factor_2) { swap(candidat , arbore[nod]); }
if (factor_1 != factor_2) { Insert(2 * nod , stanga , mijloc , candidat); }
else { Insert(2 * nod + 1 , mijloc + 1 , dreapta , candidat); }
}
pair <long long , int> Query (const int nod , const int stanga , const int dreapta , const int indice)
{
if (stanga == dreapta)
{ return make_pair(1e18 , 0); }
pair <long long , int> candidat;
const int mijloc = (stanga + dreapta) >> 1;
if (indice <= mijloc) { candidat = Query(2 * nod , stanga , mijloc , indice); }
else { candidat = Query(2 * nod + 1 , mijloc + 1 , dreapta , indice); }
return min(candidat , make_pair(arbore[nod].first(indice) , arbore[nod].second));
}
long long take_photos (int cantitate , int lungime , int limita , vector <int> __linie , vector <int> __coloana)
{
coordonate.resize(cantitate);
for (int indice = 0 ; indice < cantitate ; indice++)
{
coordonate[indice].first = __linie[indice];
coordonate[indice].second = __coloana[indice];
if (coordonate[indice].first > coordonate[indice].second)
{ swap(coordonate[indice].first , coordonate[indice].second); }
}
sort(coordonate.begin() , coordonate.end() , [] (pair <int , int>& optiune_1 , pair <int , int>& optiune_2) -> bool {
return optiune_1.second != optiune_2.second ? optiune_1.second < optiune_2.second : optiune_1.first > optiune_2.first;
});
{ int ramas = 1;
for (int indice = 1 ; indice < cantitate ; indice++) {
while (ramas && coordonate[ramas - 1].first >= coordonate[indice].first)
{ ramas--; }
coordonate[ramas++] = coordonate[indice];
}
coordonate.resize(ramas);
cantitate = ramas;
}
coordonate.resize(cantitate + 1);
for (int indice = cantitate ; indice ; indice--)
{ coordonate[indice] = coordonate[indice - 1]; }
coordonate[0] = {-1 , -1};
long long inceput = 0 , sfarsit = 1e12;
while (inceput <= sfarsit)
{
pair <long long , int> minim;
const long long termen = (inceput + sfarsit) / 2;
for (int dreapta = 1 ; dreapta <= cantitate ; dreapta++)
{
Insert(1 , 0 , lungime , {{-2 * coordonate[dreapta].first , termen + minim.first + 1LL * coordonate[dreapta].first * coordonate[dreapta].first - 1LL * max(0 , coordonate[dreapta - 1].second - coordonate[dreapta].first + 1) * max(0 , coordonate[dreapta - 1].second - coordonate[dreapta].first + 1) - 2 * coordonate[dreapta].first} , minim.second + 1});
minim = Query(1 , 0 , lungime , coordonate[dreapta].second);
minim.first += 1LL * (coordonate[dreapta].second + 1) * (coordonate[dreapta].second + 1);
}
if (minim.second <= limita)
{ sfarsit = termen - 1; }
else
{ inceput = termen + 1; }
for (int nod = 1 ; nod < 2 * lungime ; nod++)
{ arbore[nod] = { }; }
}
pair <long long , int> minim;
const long long termen = inceput;
for (int dreapta = 1 ; dreapta <= cantitate ; dreapta++)
{
Insert(1 , 0 , lungime , {{-2 * coordonate[dreapta].first , termen + minim.first + 1LL * coordonate[dreapta].first * coordonate[dreapta].first - 1LL * max(0 , coordonate[dreapta - 1].second - coordonate[dreapta].first + 1) * max(0 , coordonate[dreapta - 1].second - coordonate[dreapta].first + 1) - 2 * coordonate[dreapta].first} , minim.second + 1});
minim = Query(1 , 0 , lungime , coordonate[dreapta].second);
minim.first += 1LL * (coordonate[dreapta].second + 1) * (coordonate[dreapta].second + 1);
}
return minim.first - termen * limita;
}
