ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1689. Рыболов и штанга

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Problem illustration
Заядлый рыболов Иван в свободное от рыбалки время любит заниматься со штангой. Он её крутит, вертит, поднимает, делает с ней, что хочет. Но во время таких тренировок в специальный полукруглый жёлоб, где обычно лежит штанга, заползают червяки — чем-то им нравится это место. Нетрудно понять, что Иван не хочет зря давить червяков — ведь они пригодятся ему в качестве наживки. Поэтому он выбирает место для штанги так, чтобы повредить как можно меньше червяков. А вы бы смогли найти такое место?
С каждой стороны штанги надето по одному блину толщины p см. Расстояние от левого края левого блина до правого края правого блина равняется b см. Длина жёлоба составляет g см. Все червяки имеют одинаковую длину w см и лежат вдоль жёлоба на его дне, не наползая друг на друга. Если хоть малая часть червяка оказывается под блином штанги, он считается повреждённым и не пригодным для рыбалки.

Исходные данные

В первой строке даны длина жёлоба g и длина червяка w (1 ≤ wg ≤ 100000). Во второй строке даны характеристики штанги b и p (1 ≤ pb/2 ≤ g/2). В третьей строке дано количество червяков n (1 ≤ n ≤ 100000). В четвёртой строке через пробел указаны координаты червяков xi, лежащие в пределах от 0 до g − w. Под координатой червяка подразумевается расстояние от его левого края до левого края жёлоба в сантиметрах.
Все величины во входных данных — целые числа.

Результат

Выведите целое число — расстояние от левого края левого блина штанги до левого края жёлоба в сантиметрах. Штанга должна повредить минимально возможное количество червяков. При равном количестве пострадавших червяков расстояние до левого края жёлоба должно быть минимальным.

Примеры

исходные данныерезультат
1000 4
500 60
10
47 68 22 237 585 417 666 996 888 555
149
20 1
2 1
11
1 2 3 4 6 8 10 12 14 16 19
17
Автор задачи: Станислав Васильев
Источник задачи: Открытое личное первенство УрГУ 2009 (28 февраля 2009)