Fişierul intrare/ieşire:	stalpi2.in, stalpi2.out	Sursă	ONI 2010, clasele 11-12
Autor	Constantin Galatan	Adăugată de	Andrei-Bogdan Antonescu •andrei-alpha
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Stalpi2

Veronel doreşte să-şi repare gardul care-i separă curtea de cea a vecinului său. Gardul este susţinut de n stâlpi, amplasaţi coliniar, numerotaţi în ordine de la stânga la dreapta: 1, 2, ..., N. Aceştia se găsesc la distanţele d_i metri (i=2, 3, ..., N) faţă de primul stâlp. Stâlpii 2, 3, ... N-1 pot fi mutaţi spre stânga sau spre dreapta. Stâlpul 1 şi stâlpul N nu se pot muta. Pentru simplitate, Veronel calculează efortul deplasării unui stâlp ca fiind egal cu distanţa de deplasare. Fie D cea mai mare distanţă dintre doi stâlpi consecutivi, după efectuarea tuturor mutărilor.

Cerinţă

Cunoscând efortul total maxim E pe care Veronel este dispus să-l facă pentru deplasarea stâlpilor să se determine cea mai mică valoare posibilă pentru D, care se poate obţine conform condiţiilor din enunţ, astfel încât să nu se depăşească efortul E. Efortul total este definit ca suma eforturilor pe care Veronel le face pentru deplasarea stâlpilor.

Date de intrare

Pe prima linie a fişierului de intrare stalpi2.in se află două numere naturale N şi E separate printr-un singur spaţiu, cu semnificaţia din enunţ. Pe linia următoare se află N–1 numere naturale d₂, d₃, ..., d_N, separate prin câte un singur spaţiu, reprezentând distanţele iniţiale ale stâlpilor 2, 3, ..., N faţă de stâlpul 1.

Date de ieşire

Fişierul de ieşire stalpi2.out va conţine o singură linie pe care se va scrie un număr natural D, cu semnificaţia din enunţ.

Restricţii

• Stâlpii pot fi mutaţi doar pe poziţii a căror distanţă faţă de stâlpul 1 este exprimată prin valori naturale.
• 0 ≤ d₂ ≤ d₃ ... ≤ d_N ≤ 10 000
• 3 ≤ N ≤ 50
• 1 ≤ E ≤ 400 000
• Pentru 20% din teste N = 3 şi d_N ≤ 100
• Pentru 40% din teste N ≤ 15 şi d_N ≤ 200
• Pentru 70% din teste N ≤ 15 şi d_N ≤ 1000
• Pentru 100% din teste N ≤ 50 şi d_N ≤ 10 000

Exemplu

Explicaţie

Se mută stâlpul 2 cu 7 metri spre dreapta şi stâlpul 3 cu 3 metri spre dreapta.

Cum se trimit solutii?