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.

题目描述

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

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

从 $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$。