Load
Турнир за Купата на Декана, 2010
Time Limit: 0.1s, Memory Limit: 64MiB
Ели си избира кола! И за разлика от повечето други жени, които гледат предимно качества от сорта на това какъв цвят е тя, дали огледалото на сенника е достатъчно голямо за да си направят грима, хубав ли е звука в колата, климатикът и парното дали са достатъчно силни и т.н., Елеонора е по-практична. За нея най-важният фактор е резервоарът. Тя наистина не обича да спира да зарежда гориво (чупи си маникюра, после ръцете ѝ миришат на нафта, губи се време и т.н), от друга страна пък твърде голям резервоар излиза по-скъпо.

Ели е готова да направи компромис, като избере кола с най-малкият резервоар, достатъчно голям за да я закара с не повече от К зареждания от тях до училище. Пътя можем да си представим като права линия, върху която на позиция 0 се намира домът ѝ, на позиция L се намира ФМИ, а между тях има N бензиностанции на позиции A1, A2, ..., AN. Можем да приемем, че колата харчи един литър гориво за единица разстояние.

Намерете минималната вместимост на резервоара, която би позволила на Ели да стигне от точка 0 до точка L с не повече от K зареждания. Приемаме, че в началото на пътуването резервоарът е пълен.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N, K и L, съответно указващи броя бензиностанции, на които Ели може да зареди, максималният брой зареждания, които Ели може да направи, и дължината на пътя от тях до университета. На следващия ред ще има N цели числа A1, A2, ..., AN, указващи позициите на бензиностанциите.
Изход
На единствен ред на стандартния изход изведете едно цяло число, указващо колко е минималната вместимост на резервоара, който отговаря на изискванията на Ели.
Ограничения
  • 0 ≤ K ≤ 1,000
  • 1 ≤ N ≤ 100,000
  • 1 ≤ L ≤ 1,000,000,000
  • 0 < А1 < А2 < ... < АN < L
Примерен Вход Примерен Изход
2 1 42 13 23 23
8 2 1337 13 133 411 730 733 911 1113 1276 500
В първия пример Ели може да спре най-много веднъж на някоя от бензиностанциите в позиции 13 и 23. Университетът се намира в позиция 42. С резервоар с вмеситмост 23 тя може да стигне от тях до втората бензиностанция, да зареди там, и после да стигне до крайната си цел. Във втория пример тя може да зареди в бензиностанциите с позиции 411 и 911.
Мрън!