往届 ACM 队训练题 (参考)

1015. 人民的救星

单点时限: 2.0 sec

内存限制: 256 MB

战争时期,防空洞具有重要作用,当防空警报响起时,大家跑进最近的防空洞避难。但如果防空洞容量不够大的话,这样往往会造成一些人的无谓牺牲。比如有 A、B、C 三个防空洞,如果 A 的容量和 B 的容量比较小,B 处的人可以选择不进入防空洞 B,而进入防空洞 C(如果时间允许),把 B 处的空间留给 A 处的人,这样让 A 处的人能进入 B 避难 (如果时间允许)。

请为 X 国的国防部设计一个能程序,对于给定的 N 个地方的人数和 N 处防空洞容量以及它们之间的连接情况,计算出所有人都进入防空洞所需的最少时间。靠你了,人民的救星!

输入格式

以两个正整数 N(1<=N<=200),M(1<=M<=1500) 开始,表示有 N 个地点,M 条路。

接下来 N 行每行整数 ai,bi 表示第 i 个地方有 ai(0<=ai<=1000) 个人,该处防空洞容量为 bi(0<=bi<=1000)。

接下来 M 行每行三个整数 a,b,c,表示 a 与 b 之间有一条路 (无向的),走这条路所需的时间为 c(1<=c<=1000000000)。

输出格式

输出所有人都进入防空洞最少需要的时间。如果不可能所有人都进入防空洞,输出-1。

样例

Input
3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120
Output
110
不限期开放

题目列表