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 di 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 stalpi1.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 d2 d3 ... dn, 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 stalpi1.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 ≤ d2 ≤ d3 ... ≤ dn ≤ 10 000
• 3 ≤ n ≤ 50
• 1 ≤ E ≤ 400 000
• Pentru 20% din teste n = 3 şi dn ≤ 100
• Pentru 40% din teste n ≤ 15 şi dn ≤ 200
• Pentru 70% din teste n ≤ 15 şi dn ≤ 1000
• Pentru 100% din teste n ≤ 50 şi dn ≤ 10 000
Exemple
stalpi1.in
stalpi1.out
Explicaţii
4 10
10 30 50
17
Se mută stâlpul 2 cu 7 metri spre dreapta şi stâlpul 3 cu 3 metri spre dreapta.