Задача K. Космическое поселение ≡

Условие

Для освоения Марса требуется построить исследовательскую базу. База должна состоять из N одинаковых модулей.

Каждый модуль представляет собой жилой отсек, который в основании имеет форму прямоугольника размером A × B метров.

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

Модуль с защитным слоем, толщина которой равна D метрам, будет иметь в основании форму прямоугольника размером (A + 2 D) × (B + 2 D) метров.

Все модули должны быть расположены на заранее подготовленном прямоугольном поле размером W × H метров.

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

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

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

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

Во втором примере жилой отсек имеет в основании размер 5 × 5 метров, а поле — размер 6 × 6 метров.

Добавить дополнительный защитный слой к модулю нельзя.

Формат входного файла

Входной файл содержит пять разделенных пробелами целых чисел: N, A, B, W, H.

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

Формат выходного файла

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

Если дополнительный защитный слой установить не удастся, требуется вывести число 0.

Ограничения

1 ≤ N, A, B, W, H ≤ 10¹⁸

Система оценки и описание подзадач

Подзадача 1 (26 баллов)

1 ≤ N ≤ 1000; 1 ≤ A, B, W, H ≤ 1000.

Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 2 (23 балла)

1 ≤ N ≤ 1000; 1 ≤ A, B, W, H ≤ 10⁹.

Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 3 (24 балла)

1 ≤ N ≤ 10⁹; 1 ≤ A, B, W, H ≤ 10¹⁸.

В этой подзадаче 8 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Подзадача 4 (27 баллов)

1 ≤ N ≤ 10¹⁸; 1 ≤ A, B, W, H ≤ 10¹⁸.

В этой подзадаче 9 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Примеры тестов

11 2 3 21 25

2

1 5 5 6 6

0