小胖和 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 \le 15
另有 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。