6172 - 例4.3 最小花费

15678424185726.png

Input

15678424435494.png

Output

输出A使得B到账100元最少需要的总费用。精确到小数点后8位。

Examples

Input

3 3
1 2 1
2 3 2
1 3 3
1 3

Output

103.07153164

Hint

【数据范围】

1<=n<=2000

Source

一本通增补1

Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题