== include(page="template/taskheader" task_id="telefon3") ==

Poveste şi cerinţă...

Dorel, plictisit de puzzle-ul pe care l-a upgradat ieri, a decis să meargă afară cu ceilalţi copii. El îi priveşte pe cei N copii cum joacă “telefonul fără fir”.
Jocul decurge în felul următor:
 
* Iniţial, copiii se aşază pe axa $**Ox**$, copilul $**i**$ la distanţa $**X{~i~}**$ metri faţă de origine.
* Copilul cel mai aproape de origine alege un cuvânt secret şi îl transmite celui din dreapta lui; cel din dreapta lui îl transmite următorului şi aşa mai departe până se ajunge la ultimul copil.
 
Pentru a transmite cuvântul, fiecare copil trebuie să meargă până la copilul din dreapta lui. Toţi copiii se deplasează cu viteza constantă de 1 metru/secundă.
 
Cu toate acestea, pentru a evita deplasarea fiecare copil dispune de un dispozitiv de tip _walkie-talkie_ ce permite transmiterea unui cuvânt mai departe. Toate staţiile _walkie-talkie_ au o rază de acţiune $**R**$, setată la începutul unei runde de joc (exprimată în metri) ce nu poate fi modificată pe parcursul jocului. Staţiile sunt conectate la aceeaşi sursă de alimentare care are $**B**$ unităţi de energie.
 
În funcţie de raza de acţiune setată, copiii pot sau nu să folosească sistemul _walkie-talkie_ pentru a nu se mai deplasa. Mai exact, dacă un copil ar trebui să parcurgă o distanţă mai mică sau egală cu $**R**$ ca să transmită cuvântul celui din dreapta sa şi bateria sursei are cel puţin $**R**$ unităţi de energie rămase, acesta poate folosi sistemul _walkie-talkie_ ca să transmită instantaneu cuvântul secret, iar bateria se va descărca cu $**R**$ unităţi de energie. Cu toate acestea, chiar şi cu sistemul _walkie-talkie_, un copil nu are voie să
transmită mesajul decât primului copil situat în dreapta lui.
 
Copiii doresc ca jocul să se termine cât mai repede, aşa că vor seta o rază de acţiune convenabilă şi vor alege să folosească sau nu sistemul _walkie-talkie_, pentru a minimiza timpul necesar ca toţi cei $**N**$ copii să afle cuvântul secret.
 
Dorel doreşte să se alăture jocului, aşa că în a doua parte a jocului va intra şi el în rând. Dorel se va aşeza pe axa $**Ox**$, undeva între primul şi ultimul copil, la o anumită distanţă de origine unde nu se află un alt copil
 
h2. Cerinţe
 
# Care este durata minimă a jocului, dacă Dorel nu ia parte la joc?
# Care este durata minimă a jocului, dacă Dorel ia parte la joc şi se poziţionează în mod optim
pentru a minimiza durata jocului?
 

h2. Date de intrare

Fişierul de intrare $telefon3.in$ ...

Fişierul de intrare $telefon3.in$ conţine pe prima linie două numere naturale $**N**$ şi $**B**$ cu semnificaţia din enunţ. Pe cea de-a doua linie se află $**N**$ numere naturale nenule distincte $**X{~i~}**$, în ordine strict crescătoare, unde $**X{~i~}**$ reprezintă distanţa copilului $**i**$ faţă de origine, $**1 ≤ i ≤ N**$.

h2. Date de ieşire

În fişierul de ieşire $telefon3.out$ ...

Fişierul de ieşire $telefon3.out$ va conţine două numere naturale $**C1 C2**$, separate printr-un spaţiu, unde $**C1**$ reprezintă răspunsul la cerinţa $**1**$ iar $**C2**$ răspunsul la cerinţa $**2**$.
 
 

h2. Restricţii

* $... ≤ ... ≤ ...$

* $2 ≤ N ≤ 10^5^$
* $1 ≤ B ≤ 10^9^, 1 ≤ X{~i~} ≤ 10^9^$
* $Se garantează că Dorel are cel puţin o poziţie liberă pe care se poate aşeza$
* $Un copil poate alege între a se deplasa sau a folosi _walkie-talkie_ pentru a transmite un mesaj$
* $Copiii pot seta o noua rază de acţiune a _walkie-talkie_ când Dorel intră în joc$
* $Pentru prima cerinţă se acordă 40 puncte$
* $Pentru a doua cerinţă se acordă 60 puncte$
* $Pentru teste în valoare de 15 puncte N, B ≤ 10^2^$
* $Pentru alte teste în valoare de 35 puncte N ≤ 10^3^, B ≤ 10^4^$
* $Pentru alte teste în valoare de 20 puncte N ≤ 10^5^, B ≤ 10^5^$
* $Pentru alte teste în valoare de 30 puncte N ≤ 10^5^, B ≤ 10^9^$

h2. Exemplu
table(example). |_. telefon3.in |_. telefon3.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 6 15
7 9 12 16 21 27
| 8 6

|
h3. Explicaţie

...

$N=6, B=15$
$X{~[1-6]~}=[7,9,12,16,21,27]$
 
!problema/telefon3?explicatie.png!
 
# Dacă Dorel *nu* participă la joc atunci copiii vor alege raza de acţiune R=5 şi al 2-lea, al 3-lea şi al 4-lea copil vor folosi sistemul de comunicare. În consecinţă durata jocului va fi (9-7)+(27-21)= 2+6 = 8
# Dacă Dorel participă la joc se va poziţiona la distanţa 26 faţă de origine. În această situaţie copiii vor alege raza de acţiune R tot 5 şi al 3-lea, al 4-lea şi al 5-lea copil vor folosi sistemul de comunicare. În consecinţă durata jocului va fi
(9-7)+(12-9)+(27-26) = 2+3+1 = 6
 
 
 

== include(page="template/taskfooter" task_id="telefon3") ==