#P2656. 采蘑菇
采蘑菇
题目描述
小胖和 ZYR 要去 ESQMS 森林采蘑菇。
ESQMS 森林间有 个小树丛, 条小径,每条小径都是单向的,连接两个小树丛,上面都有一定数量的蘑菇。小胖和 ZYR 经过某条小径一次,可以采走这条路上所有的蘑菇。由于 ESQMS 森林是一片神奇的沃土,所以一条路上的蘑菇被采过后,又会长出一些新的蘑菇,数量为原来蘑菇的数量乘上这条路的“恢复系数”,再下取整。
比如,一条路上有 个蘑菇,这条路的“恢复系数”为 ,则第一~四次经过这条路径所能采到的蘑菇数量分别为 。
现在,小胖和 ZYR 从 号小树丛出发,求他们最多能采到多少蘑菇。
输入格式
第一行两个整数, 和 。
第二行到第 行,每行四个数,分别表示一条小路的起点,终点,初始蘑菇数,恢复系数。
第 行,一个整数 。
输出格式
一行一个整数,表示最多能采到多少蘑菇,保证答案不超过 。
3 3
1 2 4 0.5
1 3 7 0.1
2 3 4 0.6
1
8
提示
对于 的数据,,
另有 的数据,满足所有“恢复系数”为 。
对于 的数据,,, 且最多有一位小数, 。