• Inițial, copiii se așază pe axa Ox, copilul i la distanța Xi 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ța

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 Xi, în ordine strict crescătoare, unde Xi reprezintă distanța copilului i față de origine, 1 ≤ i ≤ N.

Date de ieșire

Fișierul de ieșire telefon.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.

Restricții și precizări

• 2 ≤ N ≤ 100.000
• 1 ≤ B ≤ 1.000.000.000, 1 ≤ Xi ≤ 1.000.000.000
• 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 ≤ 100
• Pentru alte teste în valoare de 35 puncte N ≤ 1000, B ≤ 10.000
• Pentru alte teste în valoare de 20 puncte N ≤ 100.000, B ≤ 100.000
• Pentru alte teste în valoare de 30 puncte N ≤ 100.000, B ≤ 1.000.000.000

Exemplu:

telefon.in

6 15
7 9 12 16 21 27

telefon.out

8 6

Explicație

N = 6, B = 15, X[1-6] = [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 doilea, al treilea și al patrulea 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 tot 5 și al treilea, al patrulea și al cincilea copil vor folosi sistemul de comunicare.
În consecință durata jocului va fi (9-7)+(12-9)+(27-26) = 2+3+1 = 6.