A. Интеллектуальный вендинг
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В этот жаркий Санкт-Петербургский полдень стажёр Яндекса Аркадий сидел в офисе и вносил последние правки в свою дипломную работу. После нескольких часов тяжких трудов он решил развеяться и прогуляться до торгового автомата на первом этаже, чтобы купить бутылку своего любимого напитка Квас-Класс.

Стоит отметить, что в офисе установлен довольно необычный торговый автомат. Он принимает только монеты достоинством один рубль и купюры достоинством один миллион рублей, и при этом продаёт только бутылки напитка Квас-Класс ценой r рублей за штуку. Изначально у Аркадия есть b банкнот достоинством миллион рублей и c монет по одному рублю. В автомате изначально находятся d рублёвых монет, которыми он может давать сдачу. Процесс покупки одной бутылки напитка устроен следующим образом.

  1. Аркадий вставляет в автомат x банкнот и y монет, то есть общая загруженная сумма составляет z = 106·x + y.
  2. Затем он нажимает на кнопку совершения покупки. Если z оказывается меньше r, то автомат просит внести ещё денег.
  3. Если z больше либо равно r, то автомат пытается выдать Аркадию сдачу. Поскольку автомат может выдавать сдачу только монетами, то количество находящихся в нём монет в один рубль (при этом не учитываются монеты, вставленные для совершения именно этой покупки) должно быть не менее z - r. Если монет для выдачи сдачи недостаточно, то покупка не состоится.
  4. Если z ≥ r и в автомате достаточно монет для того, чтобы выдать Аркадию сдачу (или сдача вообще не требуется, то есть z = r), происходит покупка. Автомат забирает себе x банкнот и y монет (которые могут быть использованы для выдачи сдачи при следующих покупках), после чего возвращает Аркадию z - r монет и выдаёт бутылку желанного напитка.

Хотя Аркадий пришёл купить только одну бутылку, он всё же программист, так что ему интересно, какое максимально количество бутылок он смог бы приобрести, если бы действовал оптимально? Можете считать, что в автомат загружено заведомо достаточное количество бутылок напитка Квас-Класс (что, к сожалению, далеко не всегда выполнено в реальной жизни).

Входные данные

В первой строке входных данных записаны два целых числа b и c (0 ≤ b, c ≤ 109) — количество банкнот достоинством в один миллион рублей и количество монет в один рубль в распоряжении Аркадия.

Во второй строке записаны два целых числа r и d (1 ≤ r ≤ 109, 0 ≤ d ≤ 109) — цена одной бутылки напитка Квас-Класс и количество монет в торговом автомате до покупок Аркадия. Обратите внимание, что количество купюр внутри автомата значения не имеет.

Выходные данные

Выведите одно целое число равное максимальному количеству бутылок напитка Квас-Класс, которые Аркадий сможет купить если будет действовать оптимально.

Примеры
Входные данные
21 1000000
1100000 0
Выходные данные
20
Входные данные
10 700000
350000 200000
Выходные данные
4
Примечание

В первом примере Аркадий сможет потратить все свои деньги.

Во втором примере Аркадий может сначала купить две бутылки используя только имеющиеся у него монеты. Затем он купит бутылку с помощью банкноты (в автомате к этому моменту находятся 900 000 монет для выдачи сдачи). В конце он сможет купить ещё одну бутылку.