Description

Xiaopang and ZYR are going to the ESQMS forest to pick mushrooms.

In the ESQMS forest, there are $N$ small thickets and $M$ paths. Each path is directed, connects two thickets, and has some mushrooms on it. When Xiaopang and ZYR traverse a path once, they can collect all the mushrooms on that path. Because the ESQMS forest is a magical fertile land, after the mushrooms on a path are picked, new mushrooms will grow on that path again, with the quantity equal to the original number of mushrooms multiplied by the path’s "recovery factor", then rounded down.

For example, if a path initially has $4$ mushrooms and its "recovery factor" is $0.7$, then the numbers of mushrooms that can be collected on the first through fourth traversals are $4, 2, 1, 0$ respectively.

Now, starting from thicket $S$, find the maximum number of mushrooms they can collect.

Input Format

The first line contains two integers, $N$ and $M$.

From the second line to the $(M+1)$-th line, each line contains four numbers, representing the start thicket, the end thicket, the initial number of mushrooms, and the recovery factor of a path.

The $(M+2)$-th line contains an integer $S$.

Output Format

Output one line with a single integer, the maximum number of mushrooms that can be collected. It is guaranteed that the answer does not exceed $(2^{31}-1)$.

3 3
1 2 4 0.5
1 3 7 0.1
2 3 4 0.6
1

8

Hint

For $30\%$ of the testdata, $N\le 7$, $M\le15$.

For another $30\%$ of the testdata, all "recovery factors" are $0$.

For $100\%$ of the testdata, $1\le N\le 8\times 10^4$, $1\le M\le 2\times 10^5$, $0\le\text{恢复系数}\le 0.8$ with at most one decimal place, and $1\le S\le N$.

Translated by ChatGPT 5