D. Профессор Хаос

D. Профессор Хаос

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

Решение задачи

В секретной лаборатории профессора Хаоса проходит эксперимент по выращиванию особо опасных бактерий. В начале первого дня эксперимента у Хаоса имеется $a$ особо опасных бактерий.

Каждый день эксперимента устроен следующим образом. Рано утром профессор достает из контейнера все свои бактерии и помещает их в инкубатор, где бактерии начинают делиться. Вместо каждой бактерии образуется $b$ новых бактерий.

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

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

Теперь профессор Хаос хочет выяснить, сколько особо опасных бактерий будет у него в контейнере после $k$-го дня эксперимента. Помогите ему найти ответ на этот вопрос.

Формат ввода

В единственной строке входного файла содержится пять целых чисел $a$, $b$, $c$, $d$ и $k$ $(1 \leq a, b \leq 1000, 0 \leq c \leq 1000, 1 \leq d \leq 1000, a \leq d, 1 \leq k \leq 1018)$.

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

Выведите одно число — количество бактерий у Хаоса к концу $k$-го дня. Если эксперимент завершится в $k$-й день или ранее, выведите число 0.

Пример 1

Ввод	Вывод
1 3 1 5 2	5

Пример 2

Ввод	Вывод
1 2 0 4 3	4

Пример 3

Ввод	Вывод
1 2 3 5 2	0

Скачать условие задачи