Farmer Nikolai hired two lumberjacks: Dmitry and Fedor, to cut down the forest, in the place of which there should be a cornfield.
X trees grow in the forest.
Dmitry cuts
A trees a day, but every
K day he rests and does not cut a single tree. Thus, Dmitry rests on the
K-th,
2K-th,
3K-th day, etc.
Fedor cuts down
B trees a day, but every
M-th day he rests and does not cut a single tree. Thus, Fedor rests on the
M-th,
2M-th,
3M-th day, etc.
The lumberjacks work in parallel and thus, on days when none of them rests, they cut down
A + B trees, on days when only Fedor —
A trees, and on days when only Dmitry —
B trees. On days when both loggers rest, not a single tree is cut down.
Farmer Nikolai wants to know how many days it will take the loggers to cut down all the trees and he can sow the cornfield. It is required to write a program that given integers
A,
K,
B,
M and
X< /code> determines how many days it takes for all trees in the forest to be cut down.
Input: five space-separated integers are input: A, K, B, M and X (\(1 <= A,\ B <= 10^9 \) , \(2 <= K,\ M <= 10^{18}\), \(1 <= X <= 10^{18}\)).
Input: print a single integer — desired number of days.
Examples
| # |
Input |
Output |
| 1 |
2 4 3 3 25 |
7 |
Explanation for example
In the example above, lumberjacks cut down 25 trees in 7 days as follows:
- 1st day: Dmitry cuts down 2 trees, Fedor cuts down 3 trees, total 5 trees;
- 2nd day: Dmitry cuts down 2 trees, Fedor cuts down 3 trees, total 10 trees;
- 3rd day: Dmitry cuts down 2 trees, Fedor rests, total 12 trees;
- 4th day: Dmitry rests, Fedor cuts down 3 trees, total 15 trees;
- 5th day: Dmitry cuts down 2 trees, Fedor cuts down 3 trees, total 20 trees;
- 6th day: Dmitry cuts down 2 trees, Fedor rests, total 22 trees;
- 7th day: Dmitry cuts down 2 trees, Fedor cuts down the remaining 1 tree, in total all 25 trees are cut down.