Космическое поселение

Для освоения Марса требуется построить исследовательскую базу. База должна состоять из n одинаковых модулей. Каждый модуль представляет собой жилой отсек, который в основании имеет форму прямоугольника размером a × b метров.

Для повышения надежности модулей инженеры могут добавить вокруг каждого модуля дополнительный защитный слой. Толщина этого слоя должна составлять целое число метров, и все модули должны иметь одинаковую толщину защитного слоя. Модуль с защитным слоем, толщина которого равна d метрам, будет иметь в основании форму прямоугольника размером (a + 2d) × (b + 2d) метров.

Все модули должны быть расположены на заранее подготовленном прямоугольном поле размером w × h метров. При этом они должны быть организованы в виде регулярной сетки: их стороны должны быть параллельны сторонам поля, и модули должны быть ориентированы одинаково.

Требуется написать программу, которая по заданным количеству и размеру модулей, а также размеру поля для их размещения, определяет максимальную толщину дополнительного защитного слоя, который можно добавить к каждому модулю.

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

Входной файл INPUT.TXT содержит пять разделенных пробелами целых чисел: n, a, b, w и h (1 ≤ n, a, b, w, h ≤ 10¹⁸). Гарантируется, что без дополнительного защитного слоя все модули можно разместить в поселении описанным образом.

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

Выходной файл OUTPUT.TXT должен содержать одно целое число: максимальную возможную толщину дополнительного защитного слоя. Если дополнительный защитный слой установить не удастся, требуется вывести число 0.

Примеры

Пояснение к примерам

В первом примере можно установить дополнительный защитный слой толщиной 2 метра и разместить модули на поле, как показано на рисунке.

Во втором примере жилой отсек имеет в основании размер 5 × 5 метров, а поле – размер 6 × 6 метров. Добавить дополнительный защитный слой к модулю нельзя.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]