Центр поддержки одаренных детей ХКИРО

В одной театральной кассе есть в продаже билеты любой стоимости, выражающейся натуральным числом. При покупке билетов по цене за билет от A до B рублей включительно нужно дополнительно оплатить сервисный сбор в размере C процентов от номинальной стоимости билетов (сервисный сбор не обязательно выражается целым числом рублей, но всегда выражается целым числом копеек). При покупке билетов стоимостью менее A рублей за билет, а также более B рублей за билет, сервисный сбор не берется.
У вас есть X рублей и вам нужно K билетов одинаковой цены (цена обязательно должна выражаться натуральным числом рублей, 0 не считается натуральным). Билеты какого самого дорогого номинала вы можете себе позволить?

Максимальное время работы на одном тесте: 1 секунда
Максимальный объем используемой памяти: 64 мегабайта

Входные данные
Вводятся целые A, B, C, X, K (1 ≤ A ≤ B ≤ 10^9, 0 ≤ C ≤ 1000, 0 ≤ X ≤ 10^9, 1 ≤ K ≤ 100000).

Выходные данные
Если на имеющиеся деньги невозможно приобрести ни одного билета, выведите 0. Иначе выведите натуральное число – номинальную стоимость приобретённых билетов.

Примеры

Домик черепахи расположен в начале прямой узкой грядки, на которой должны прорасти одуванчики – ее любимое лакомство. И вот черепахе приснился вещий сон. Из него она узнала, что наконец-то после полуночи начнут расти одуванчики. Ей даже приснилось, в какой момент времени, и в какой точке грядки вырастет каждый одуванчик. Ровно в полночь черепаха выползла из домика, чтобы съесть все одуванчики и до следующей полуночи вернуться домой.
Черепаха может ползти со скоростью, не превосходящей величины vmax. Одуванчик она съедает, остановившись на время d. Если одуванчик начать есть, но не доесть до конца, то он засыхает, поэтому его надо съедать за один прием. Одуванчики прорастают тем позже, чем дальше они расположены от начала грядки. В одной точке не могут прорастать несколько одуванчиков, а также несколько одуванчиков не могут прорастать в один момент времени.
Требуется определить, в какой момент времени черепаха сможет вернуться домой, съев все одуванчики и затратив на путешествие наименьшее время.

Входные данные
В 1-й строке входного файла находятся 2 целых числа, разделенные пробелом: vmax (в см/мин) и d (в минутах), 0 < vmax ≤ 200, 0 ≤ d ≤ 500.
Во 2-й строке находится число N – количество одуванчиков (в штуках). 0 ≤ N ≤ 1400 при d = 0, в противном случае 0 ≤ N ≤ 200.
В каждой из последующих N строк расположены: целое число xi – расстояние от одуванчика до начала грядки (в сантиметрах), 0 ≤ xi ≤ 32767, и через пробел ti – момент прорастания одуванчика (в формате hh:mm). Пары приведены в порядке возрастания расстояний.

Выходные данные
Выходной файл должен содержать момент времени возвращения черепахи домой (в формате hh:mm), округленный до целых минут в большую сторону.

Примечания
1. В часе – 60 минут, в сутках – 24 часа.
2. Время в сутках изменяется от 00:00 до 23:59.
3. Можете считать, что черепаха не меняет направления движения до тех пор, пока не доползет до последнего одуванчика.

Пример

На прямой расположены стойла, в которые необходимо расставить коров так, чтобы минимальное расстояние между коровами было как можно больше.

Входные данные
В первой строке вводятся числа N (2 < N < 10001) – количество стойл и K (1 < K < N ) – количество коров. Во второй строке задаются N натуральных чисел в порядке возрастания – координаты стойл (координаты не превосходят 10^9).

Выходные данные
Выведите одно число – наибольшее возможное допустимое расстояние.

Пример

Дано два массива. Для каждого элемента второго массива определите, сколько раз он встречается в первом массиве.

Ограничение по времени: 1 секунда
Ограничение по памяти: 64 мегабайта

Входные данные
Первая строка входных данных содержит одно число N (1 ≤ N ≤ 10^5) – количество элементов в первом массиве. Далее идет N целых чисел, не превосходящих по модулю 10^9 – элементы первого массива, Далее идет количество элементов M во втором массиве и M элементов второго массива с такими же ограничениями.

Выходные данные
Выведите M чисел: для каждого элемента второго массива выведите, сколько раз такое значение встречается в первом массиве.

Пример

Входные данные
В первой строке входных данных содержатся натуральные числа N и K (0 < N ,K <= 100000 ). Во второй строке задаются N элементов первого массива, отсортированного по возрастанию, а в третьей строке – K элементов второго массива. Элементы обоих массивов - целые числа, каждое из которых по модулю не превосходит 10^9.

Выходные данные
Требуется для каждого из K чисел вывести в отдельную строку "YES", если это число встречается в первом массиве, и "NO" в противном случае.

Пример