You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小胖和 ZYR 要去 ESQMS 森林采蘑菇。

ESQMS 森林间有 $N$ 个小树丛，$M$ 条小径，每条小径都是单向的，连接两个小树丛，上面都有一定数量的蘑菇。小胖和 ZYR 经过某条小径一次，可以采走这条路上所有的蘑菇。由于 ESQMS 森林是一片神奇的沃土，所以一条路上的蘑菇被采过后，又会长出一些新的蘑菇，数量为原来蘑菇的数量乘上这条路的“恢复系数”，再下取整。

比如，一条路上有 $4$ 个蘑菇，这条路的“恢复系数”为 $0.7$，则第一~四次经过这条路径所能采到的蘑菇数量分别为 $4,2,1,0$。

现在，小胖和 ZYR 从 $S$ 号小树丛出发，求他们最多能采到多少蘑菇。

输入格式

第一行两个整数，$N$ 和 $M$。

第二行到第 $M+1$ 行，每行四个数，分别表示一条小路的起点，终点，初始蘑菇数，恢复系数。

第 $M+2$ 行，一个整数 $S$。

输出格式

一行一个整数，表示最多能采到多少蘑菇，保证答案不超过 $(2^{31}-1)$。

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

8

提示

对于 $30\%$ 的数据，$N\le 7$，$M\le15$

另有 $30\%$ 的数据，满足所有“恢复系数”为 $0$。

对于 $100\%$ 的数据，$1 \le N\le 8\times 10^4$，$1\le M\le 2\times 10^5$，$0\le\text{恢复系数}\le 0.8$ 且最多有一位小数， $1\le S\le N$。