Поиск

Вырубка леса


Ограничение времени      1 секунда
Ограничение памяти 256Mb
Ввод forest.in
Вывод forest.out

Фермер Николай нанял двух лесорубов: Дмитрия и Федора, чтобы вырубить лес, на месте которого должно быть кукурузное поле. В лесу растут X деревьев.

Дмитрий срубает по A деревьев в день, но каждый K-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в K-й, 2K-й, 3K-й день, и т.д.

Федор срубает по B деревьев в день, но каждый M-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в M-й, 2M-й, 3M-й день, и т.д.

Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают A + B деревьев, в дни, когда отдыхает только Федор — A деревьев, а в дни, когда отдыхает только Дмитрий — B деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.

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

Требуется написать программу, которая по заданным целым числам A, K, B, M и X определяет, за сколько дней все деревья в лесу будут вырублены.

Формат ввода

Входной файл содержит пять целых чисел, разделенных пробелами: A, K, B, M и X (1 ≤ A, B ≤ 109, 2 ≤ K, M ≤ 1018, 1 ≤ X ≤ 1018).

Формат вывода

Выходной файл должен содержать одно целое число — искомое количество дней.

Пример

Ввод

2 4 3 3 25

Вывод

7

Примечания

В приведенном примере лесорубы вырубают 25 деревьев за 7 дней следующим образом:

  • 1-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 5 деревьев;
  • 2-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 10 деревьев;
  • 3-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 12 деревьев;
  • 4-й день: Дмитрий отдыхает, Федор срубает 3 дерева, итого 15 деревьев;
  • 5-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 20 деревьев;
  • 6-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 22 дерева;
  • 7-й день: Дмитрий срубает 2 дерева, Федор срубает оставшееся 1 дерево, итого все 25 деревьев срублены.


Внимание! Тест из примера не подходит под ограничения для подзадач 2 и 3, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест даже, если оно рассчитано на решение только каких-либо из подзадач 2 и 3.

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

Подзадача 1 (32 балла)
1 ≤ X ≤ 1000, 1 ≤ A, B ≤ 1000, 2 ≤ K, M ≤ 1000
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 2 (10 баллов)
1 ≤ X ≤ 1018
X < K
X < M
При решении этой подзадачи можно считать, что лесорубы не отдыхают.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 3 (10 баллов)
1 ≤ X ≤ 1018
Дополнительно к приведенным ограничениям выполняется условие K = M.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 4 (48 баллов)
1 ≤ X ≤ 1018, 1 ≤ A, B ≤ 109, 2 ≤ K, M ≤ 1018
В этой подзадаче 16 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

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


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