Ana pleaca in drumetie de la kilometrul 0 si trebuie sa ajunga la cabana aflata la kilometrul d. Pe traseu se afla k izvoare, la kilometrii a_1 < a_2 < ... < a_k. Ana are o sticla care incape g portii de apa si pleaca de acasa cu sticla plina. Pentru fiecare kilometru parcurs, Ana bea o portie de apa; daca sticla este goala, parcurge acel kilometru insetata. La fiecare izvor isi umple sticla pana la capacitatea maxima.
Ana accepta sa parcurga insetata cel mult t kilometri in total. Determinati capacitatea minima g a sticlei pentru care acest lucru este posibil.
- Date de intrare
- Pe prima linie se afla numerele d, k si t. Pe a doua linie se afla k numere naturale strict crescatoare: pozitiile izvoarelor (daca k = 0, linia este goala).
- Date de iesire
- Se afiseaza un singur numar natural: capacitatea minima g (poate fi si 0).
- Restrictii
- 1 <= d <= 1 000 000 000 0 <= k <= 200 000 0 < a_1 < a_2 < ... < a_k < d 0 <= t <= d
Exemple
Exemplul 1
Intrare
10 2 3 4 7
Iesire
3
Exemplul 2
Intrare
12 3 0 2 5 11
Iesire
6