2. Wholesale — cheaper?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Peter and his friends are going to celebrate the successful end of the school year. For this, they decided to buy $$$n$$$ packs of orange juice and $$$m$$$ packs of apple juice and allocated $$$s$$$ rubles (russian currency) for these purposes.

One pack of any juice costs $$$r$$$ rubles. However, juice can also be bought by boxes. One box contains $$$k$$$ packs of juice of one kind and costs $$$p$$$ rubles (it is known that $$$k \cdot r \gt p$$$).

The friends want to buy as many packs of juice as possible with the money they have, but so that there are at least $$$n$$$ packs of orange juice and at least $$$m$$$ packs of apple juice.

How many packs of juice can the friends buy under these conditions?

Input

The first line contains an integer $$$n$$$ $$$(1 \le n \le 5 \cdot 10^5)$$$ — the required number of packs of orange juice.

The second line contains an integer $$$m$$$ $$$(1 \le m \le 5 \cdot 10^5)$$$ — the required number of packs of apple juice.

The third line contains an integer $$$r$$$ $$$(1 \le r \le 1000)$$$ — the price of one pack of juice (of any kind).

The fourth line contains an integer $$$k$$$ $$$(2 \le k \le 10^6)$$$ — the number of packs of juice in one box.

The fifth line contains an integer $$$p$$$ $$$(1 \le p \lt k \cdot r)$$$ — the price of one box containing $$$k$$$ packs of juice.

The sixth line contains an integer $$$s$$$ $$$(1 \le s \le 10^9)$$$ — the amount of money allocated for buying juice.

Output

Print one integer — the maximum possible total number of packs of juice that can be bought.

If it is impossible to buy juice while satisfying the described conditions, print $$$-1$$$.

Scoring

Solutions that work correctly when at least one of the values $$$n$$$ or $$$m$$$ is divisible by $$$k$$$ will be awarded $$$25$$$ points.

Examples
Input
8
7
80
5
370
1400
Output
18
Input
8
7
80
5
225
1200
Output
25
Input
8
7
80
5
375
1100
Output
-1
Note

In the first example, one needs to buy $$$8$$$ packs of orange juice and $$$7$$$ packs of apple juice. One pack costs $$$80$$$ rubles, and a box of $$$5$$$ packs costs $$$370$$$ rubles. For $$$1110$$$ rubles, it is possible to buy $$$3$$$ boxes of juice, for example, two boxes of orange juice and one box of apple juice. Then $$$1400 - 3 \cdot 370 = 290$$$ rubles will remain: $$$240$$$ rubles are enough for $$$3$$$ packs of apple juice (or $$$2$$$ packs of apple juice and $$$1$$$ pack of orange juice), and $$$50$$$ rubles will remain. The conditions will be satisfied, and in total $$$3 \cdot 5 + 3 = 18$$$ packs of juice will be bought.

In the second example, for $$$1200$$$ rubles it is possible to buy $$$5$$$ boxes of juice for $$$225$$$ rubles each. If we take three boxes of orange juice and two boxes of apple juice, then the conditions will be satisfied. Then $$$1200 - 5 \cdot 225 = 75$$$ rubles will remain, and nothing can be bought with them.

In the third example, for $$$1100$$$ rubles it is possible to buy $$$2$$$ boxes of juice for $$$375$$$ rubles each: one box of orange juice and one box of apple juice. Then $$$1100 - 2 \cdot 375 = 350$$$ rubles will remain, and three more packs of orange juice and two packs of apple juice need to be bought. At a pack price of $$$80$$$ rubles, this is impossible.