Problem Description

Farmer Nikolai hired two lumberjacks, Dmitry and Fyodor, to cut down a forest so that he can plant corn there. There are $X$ trees in the forest.

Dmitry cuts down $A$ trees per day, but every $K$ days he takes a day off and cuts nothing. Therefore, Dmitry rests on days $K$, $2K$, $3K$, and so on.

Fyodor cuts down $B$ trees per day, but every $M$ days he takes a day off and cuts nothing. Therefore, Fyodor rests on days $M$, $2M$, $3M$, and so on.

The two lumberjacks work in parallel. Therefore, on days when neither rests, they cut down $A + B$ trees in total; on days when only Fyodor rests, they cut down $A$ trees; on days when only Dmitry rests, they cut down $B$ trees; and on days when both rest, they cut down nothing.

Farmer Nikolai wants to know how many days it will take the lumberjacks to cut down all the trees, so that he can start sowing corn.

Task: Write a program that, given integers $A$, $K$, $B$, $M$, and $X$, computes the number of days required for all the trees to be cut down.

Input Format

The input file contains five integers separated by spaces: $A$, $K$, $B$, $M$, and $X$ ($1 \leq A, B \leq 10^9$, $2 \leq K, M \leq 10^{18}$, $1 \leq X \leq 10^{18}$).

Output Format

The output file should contain one integer — the number of days required to cut down all the trees.

2 4 3 3 25

7

Hint

Example Explanation

In this example, the lumberjacks cut down $25$ trees in $7$ days, as follows:

• Day $1$: Dmitry cut down $2$ trees, Fyodor cut down $3$ trees, for a total of $5$ trees.
• Day $2$: Dmitry cut down $2$ trees, Fyodor cut down $3$ trees, for a total of $10$ trees.
• Day $3$: Dmitry cut down $2$ trees, Fyodor rested, for a total of $12$ trees.
• Day $4$: Dmitry rested, Fyodor cut down $3$ trees, for a total of $15$ trees.
• Day $5$: Dmitry cut down $2$ trees, Fyodor cut down $3$ trees, for a total of $20$ trees.
• Day $6$: Dmitry cut down $2$ trees, Fyodor rested, for a total of $22$ trees.
• Day $7$: Dmitry cut down $2$ trees, Fyodor cut down the remaining $1$ tree, for a total of $25$ trees cut down.

Scoring System and Subtasks Description

Subtask 1 (32 points)

• $1 \leq X \leq 1000$, $1 \leq A, B \leq 1000$, $2 \leq K, M \leq 1000$.
• You can score only if all tests are passed.

Subtask 2 (10 points)

• $1 \leq X \leq 10^{18}$.
• $X < K$.
• $X < M$.
• When solving this subtask, you may assume the lumberjacks do not rest.
• You can score only if all tests are passed.

Subtask 3 (10 points)

• $1 \leq X \leq 10^{18}$.
• An additional condition is $K = M$.
• You can score only if all tests are passed.

Subtask 4 (48 points)

• $1 \leq X \leq 10^{18}$, $1 \leq A, B \leq 10^9$, $2 \leq K, M \leq 10^{18}$.
• This subtask has $16$ tests. Each test is worth $3$ points, and each test is scored independently.

Translation source: GPT 5.2.

Translated by ChatGPT 5