stalpi

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 stalpi.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_2, d_3, ... 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 stalpi.out va conţine o singură linie pe care se va scrie un număr natural D, cu semnificaţia din enunţ.

Restricţii şi precizări

• 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_2 ≤ d_3 ... ≤ 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 ≤ 1 000$
• Pentru 100% din teste n ≤ 50 şi $d_n ≤ 10 000$

Exemplu

stalpi.in

4 10
10 30 50

stalpi.out

17

Explicaţie

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