В секретной лаборатории профессора Хаоса проходит эксперимент по выращиванию особо опасных бактерий. В начале первого дня эксперимента у Хаоса имеется \(a\) особо опасных бактерий.
Каждый день эксперимента устроен следующим образом. Рано утром профессор достает из контейнера все свои бактерии и помещает их в инкубатор, где бактерии начинают делиться. Вместо каждой бактерии образуется \(b\) новых бактерий.
После извлечения бактерий из инкубатора \(c\) из них используются для проведения различных опытов и затем уничтожаются. Если после извлечения из инкубатора имеется менее \(c\) бактерий, для проведения опытов используются все имеющиеся бактерии, и эксперимент заканчивается.
Оставшиеся бактерии в конце дня необходимо поместить в контейнер и продолжить использовать в эксперименте. Однако в контейнер можно поместить не более \(d\) бактерий, поэтому если число оставшихся бактерий больше \(d\), то в контейнер помещаются \(d\) бактерий, а остальные уничтожаются.
Теперь профессор Хаос хочет выяснить, сколько особо опасных бактерий будет у него в контейнере после \(k\)-го дня эксперимента. Помогите ему найти ответ на этот вопрос.
Формат входных данных
В единственной строке входного файла содержится пять целых чисел \(a\), \(b\), \(c\), \(d\) и \(k\) (\(1 \le a, b \le 1000\), \(0 \le c \le 1000\), \(1 \le d \le 1000\), \(a \le d\), \(1 \le k \le 10^{18}\)).
Формат выходных данных
Выведите одно число — количество бактерий у Хаоса к концу \(k\)-го дня. Если эксперимент завершится в \(k\)-й день или ранее, выведите число 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 3 1 5 2
|
5
|
|
2
|
1 2 0 4 3
|
4
|
|
3
|
1 2 3 5 2
|
0
|