| Codeforces Round 398 (Div. 2) |
|---|
| Закончено |
Наконец-то! Васе исполнилось 14 лет, а значит, пора получать паспорт! Для этого ему необходимо обратиться в паспортный стол. Но не все так просто. В паспортном столе работает только одно окно по приему документов, а очередь в него иногда занимают задолго до его открытия. Вася хочет подать документы завтра.
Он знает, что окно начинает работать спустя ts минут после полуночи, а закрывается спустя tf после полуночи (то есть (tf - 1) — последняя минута, когда окно еще работает). На прием документов от одного человека тратится ровно t минут. Если до закрытия окна остается меньше t минут, то обслуживание новых посетителей прекращается.
Ещё Вася знает, что завтра придет ровно n посетителей. Для каждого посетителя Вася знает время, в которое он придет. Каждый приходящий посетитель занимает очередь в окно, и не уходит, пока его не обслужат (или пока окно по приему документов не закроется). Если в момент прихода посетителя окно свободно (в частности, если в этот же момент закончили обслуживать предыдущего посетителя), то пришедшего посетителя начинают сразу же обслуживать.
Времена приходов всех посетителей положительны, Вася, если надо, может прийти и в нулевой момент времени (т. е. ровно в полночь), однако он не может прийти в момент времени, выражающийся нецелым числом минут после полуночи. Если Вася приходит одновременно с несколькими посетителями, то он пропускает их вперед и встает в конец очереди.
Вася, безусловно, хочет прийти так, чтобы успеть подать документы до закрытия окна. Но из всех таких вариантов он хочет выбрать такой, чтобы стоять в очереди как можно меньше. Помогите ему.
В первой строке входных данных находятся три положительных целых числа: время открытия окна ts, время закрытия окна tf и время обслуживания одного человека t. В следующей строке дано одно целое число n — количество посетителей (0 ≤ n ≤ 100 000). В третьей строке перечислены положительные целые числа в порядке неубывания — времена, в которые посетители приходят в паспортный стол.
Все времена заданы в минутах и не превосходят 1012; гарантируется, что ts < tf. Также гарантируется, что Вася может прийти так, чтобы успеть подать документы до закрытия окна.
В выходной файл выведите одно целое неотрицательное число — время, когда должен прийти Вася. Если Вася приходит одновременно с несколькими посетителями, то он пропускает их вперед и встает в конец очереди. Если оптимальных решений несколько, выведите любое.
10 15 2
2
10 13
12
8 17 3
4
3 4 5 8
2
В первом примере первый посетитель приходит точно к открытию окна, и его обслуживают две минуты. В момент времени 12 минут окно освобождается, и, если Вася подойдет к этому моменту, то его обслужат без очереди, т.к. следующий посетитель подойдет только в момент времени 13 минут.
Во втором примере, чтобы успеть подать документы, Васе надо прийти раньше всех.
