题目描述

小明和小华结伴去翠竹林采蘑菇。翠竹林中有 $N$ 个林间空地，$M$ 条单向小径，每条小径连接两个空地，上面长着若干蘑菇。

经过一条小径时，可以采走该路径上当前所有的蘑菇。采过之后，蘑菇会按照这条小径的“再生率”重新生长，新长出的蘑菇数量等于采走数量乘以再生率并下取整。

例如，某条小径上有 $4$ 朵蘑菇，再生率为 $0.7$，则前四次经过时采到的蘑菇数分别为 $4, 2, 1, 0$。

小明和小华从 $S$ 号空地出发，求他们最多能采到多少蘑菇。

输入格式

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

接下来 $M$ 行，每行四个数 $u, v, w, r$，分别表示一条小径的起点、终点、初始蘑菇数和再生率（最多一位小数）。

第 $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 r \le 0.8$ 且最多一位小数，$1 \le S \le N$。