Fişierul intrare/ieşire:	dragonball.in, dragonball.out	Sursă	Lot Mehedinți 2015 - Baraj 6 Seniori
Autor	Eugenie Daniel Posdarascu	Adăugată de	Tatomir Alex •atatomir
Timp execuţie pe test	0.15 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Dragon Ball

Goku este pus într-o situaţie FĂRĂ PRECEDENT: trebuie să parcurgă o mlaştină de lungime L (mlaştina poate fi văzută ca un segment de lungime L pe axa OX). Goku, împreună cu prietenul lui, Krillin, trebuie să parcurgă mlaştina dintr-un capăt în celălalt (aceştia se află la poziţia 0 şi trebuie să ajungă la poziţia L). N scânduri se află la anumite poziţii distincte in mlaştină. Din moment ce Goku nu poate ajunge direct la destinaţie, acesta se va folosi de cele N scânduri si de saltul ţestoasei. Goku poate sa ajungă de la o scândură (situată la poziţia x) la o altă scândură (situată la poziţia y) dacă distanţa dintre cele 2 scânduri (adica y - x) este mai mică sau egală ca D ( D fiind abilitatea lui Goku de a sări). Krillin s-a facut util şi a adus T scânduri suplimentare (pe care le cară în spate). Să se determine abilitatea minimă D necesară ca Goku să ajungă din poziţia 0 in poziţia L, ştiind că acesta poate poziţiona cele T scânduri suplimentare cum vrea el.

Date de intrare

Pe prima linie a fişierului de intrare dragonball.in se vor afla un număr natural N, un număr natural T şi un număr natural natural L. Pe următoarele N linii vor fi cele N numere naturale reprezentând cele N pozitii ale scândurilor.

Date de ieşire

În fişierul de ieşire dragonball.out se va afişa abilitatea minimă D necesară pentru ca Goku să ajungă dintr-un capăt al mlaştinii în celălalt.

Restricţii

• 1 ≤ N, T ≤ 1 000
• 1 ≤ L ≤ 10^{10 000}
• Pentru 20% din teste L ≤ 10⁹
• Pentru 40% din teste L ≤ 10⁵⁰
• Poziţiile celor N scânduri sunt distincte, sortate crescător şi fac parte din intervalul [1, L – 1].
• Krillin îl urmăreşte tot timpul pe Goku.

Exemplu

Cum se trimit solutii?