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