telefon

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

Cerință

Să se scrie un program care să rezolve următoarele cerințe:

1. Care este durata minimă a jocului, dacă Dorel nu ia parte la joc?
2. Care este durata minimă a jocului, dacă Dorel ia parte la joc şi se poziţionează în mod optim pentru a minimiza durata jocului?

Date de intrare

Fişierul de intrare telefon.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 \leq i \leq N$.

Date de ieșire

Fişierul de ieşire telefon.out va conţine două numere naturale $C_1$ și $C_2$, separate printr-un spaţiu, unde $C_1$ reprezintă răspunsul la cerinţa $1$ iar $C_2$ răspunsul la cerinţa $2$.

Restricții și precizări

• $2 \leq N \leq 10^5$
• $1 \leq B, X_i \leq 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 teste în valoare de 15 puncte $N, B \leq 10^2$.
• Pentru alte teste în valoare de 35 puncte $N \leq 10^3, B \leq 10^4$.
• Pentru alte teste în valoare de 20 puncte $N \leq 10^5, B \leq 10^5$.
• Pentru alte teste în valoare de 30 puncte $N \leq 10^5, B \leq 10^9$.
• Pentru prima cerinţă se acordă 40 de puncte.
• Pentru a doua cerinţă se acordă 60 de puncte.
• Indiferent de cerința pe care doriți să o rezolvați, fișierul de ieșire trebuie să respecte regulile menționate anterior!

Exemplu

telefon.in

6 15
7 9 12 16 21 27

telefon.out

8 6

Explicație

$N = 6$, $B = 15$ și $X = [7, 9, 12, 16, 21, 27]$

1. 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$
2. 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 =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$