配点: 600 点
問題文
*Kitamu 是帮助撰写此问题的人的名字。而且,Kitamu的女朋友不是伊吕波。
今天是北木和女友期待已久的“第一次一起采花”周年纪念日。他今天是 K 我应该送她一朵书花。然而,他有太多的纪念日需要处理,忘记了买花。于是他决定在上学的路上买些花。
在 Kitamu 居住的小镇上, 有 N 个站,每个站有 它的编号为 1~N 。另外,他使用的铁路是 M 有铁轨。 i 主线为收费站 C_i 日元2津野站 A_i 和 我讨厌 B_i 并且可以交换。车站 j 所以 X_j 书花一套 Y_j 用日元可以买任意数量的东西。他是车站 他住在 1 附近,他的学校在车站附近。 位于 N 附近。
好吧,我需要他。 K 购买超过一本书的鲜花后,到达学校的交通和鲜花的总费用最低是多少?
制約
- 输入全为整数。
- 2 \leq N \leq 1000
- 1 \leq M \leq 2000
- 1 \leq K \leq 1000
- 1 \leq A_i,B_i \leq N (1 \leq i \leq M)
- 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
- 0 \leq X_j \leq K (1 \leq j \leq N)
- 1 \leq Y_j \leq 10^9 (1 \leq j \leq N)
2019/05/01 21:32 附录:一些限制 有一个错误,显示为 N 是 这将是第 M 、 M 是 这将是第 N ,因此已更正。
入力
输入是按以下格式从标准输入给出的。
N M K A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
北穆加 K 购买100多朵花后,将上学交通费和鲜花的最低总费用打印成一行。然而,花 K 如果您买不起更多的书或无法去学校
输出-1。
入力例 1
4 3 10 1 2 100 2 3 100 3 4 100 3 10 5 20 10 1000 1 8
出力例 1
338
駅 1 从车站 车站经 2 、駅 3 转至 4 。总运输成本为 300 变成日元。车站 1 在 3 设置,站 4 在 1 如果您购买一套,鲜花的总成本将为 38 变成日元。
入力例 2
4 4 3 1 2 50 2 3 50 3 4 100 3 1 100 2 500 2 200 2 500 2 500
出力例 2
600
鲜花购买 K 请注意,它可以不仅仅是一本书。
入力例 3
2 1 1 1 2 1 0 1 0 1
出力例 3
-1
入力例 4
10 16 10 6 10 3 3 1 4 2 3 9 8 8 8 10 4 10 6 5 9 2 3 1 7 4 3 8 2 2 6 10 9 8 6 10 8 3 4 7 8 2 6 4 6 8 7 9 9 6 7 5 10 4 3 7 7 1 8 3 8 5 1 6 3 1 7 2 8 7 8
出力例 4
22