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