#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
static vector < pair <int , int> > coordonate;
static pair <int , long long> candidat[100001];
static pair <long long , int> minim[100001];
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)
{
const long long termen = (inceput + sfarsit) / 2;
for (int dreapta = 1 ; dreapta <= cantitate ; dreapta++)
{
candidat[dreapta] = {-2 * coordonate[dreapta].first , termen + minim[dreapta - 1].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[dreapta].first = INT64_MAX;
for (int stanga = 1 ; stanga <= dreapta ; stanga++)
{ minim[dreapta] = min(minim[dreapta] , {1LL * candidat[stanga].first * coordonate[dreapta].second + candidat[stanga].second , minim[stanga - 1].second + 1}); }
minim[dreapta].first += 1LL * (coordonate[dreapta].second + 1) * (coordonate[dreapta].second + 1);
}
if (minim[cantitate].second <= limita)
{ sfarsit = termen - 1; }
else
{ inceput = termen + 1; }
}
const long long termen = inceput;
for (int dreapta = 1 ; dreapta <= cantitate ; dreapta++)
{
minim[dreapta].first = INT64_MAX;
for (int stanga = 1 ; stanga <= dreapta ; stanga++)
{ minim[dreapta] = min(minim[dreapta] , {termen + minim[stanga - 1].first - 1LL * max(0 , coordonate[stanga - 1].second - coordonate[stanga].first + 1) * max(0 , coordonate[stanga - 1].second - coordonate[stanga].first + 1) + 1LL * (coordonate[dreapta].second - coordonate[stanga].first + 1) * (coordonate[dreapta].second - coordonate[stanga].first + 1) , minim[stanga - 1].second + 1}); }
}
return minim[cantitate].first - termen * limita;
}
