dragonball

Dragon Ball

== include(page="template/taskheader" task_id="dragonball") ==

Poveste şi cerinţă...

!>problema/dragonball?img.png!
 
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.

h2. Date de intrare

Fişierul de intrare $dragonball.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $dragonball.out$ ...

Î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.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N, T ≤ 1 000$
* $1 ≤ L ≤ 10^10 000^$
* $Pentru 20% din teste L ≤ 10^9^$
* $Pentru 40% din teste L ≤ 10^50^$
* $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.$

h2. Exemplu
table(example). |_. dragonball.in |_. dragonball.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 5 100
10
13
50
69
88
| 12

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="dragonball") ==