配点 : 450 点
問題文
在 AtCoder Land 有 N 一个地点和 M 条道路。i 第 个道路连接地点 a_i 和 b_i 双向,通行需要 d_i 分钟。
接下来,在 AtCoder Land 将 K 举办 个活动。i 参加第 个活动,需要在时刻 t_i 分钟到达地点 c_i 。活动持续时间为 0 分钟。
你在时刻 0 分钟到达地点 1 在。请在适当行动时,求出最多可以参加多少个活动。
制約
- 1 \leq N \leq 1000
- 0 \leq M \leq 1000
- 1 \leq K \leq 1000
- 1 \leq a_i < b_i \leq N
- i \neq j 的话 (a_i, b_i) \neq (a_j, b_j)
- 1 \leq d_i \leq 10^9
- 1 \leq c_i \leq N
- 1 \leq t_i \leq 10^9
- i \neq j 的话 (c_i,t_i) \neq (c_j,t_j)
- 输入全部为整数
入力
输入将以以下形式从标准输入给出。
N M K a_1 b_1 d_1 a_2 b_2 d_2 \vdots a_M b_M d_M c_1 t_1 c_2 t_2 \vdots c_K t_K
出力
输出答案。
入力例 1
3 3 3 1 2 1 1 3 3 2 3 7 1 8 2 2 3 7
出力例 1
2
例如,通过如下行动,2 可以参加某个活动。
- 开始时,时间 0 分钟到达地点 1 在
- 道 1 经过时间 1 分钟到达地点 2 在
- 時刻 2 分钟到达地点 2 参加活动 参加 2 因为不能参加超过
- 道 1 经过时间 3 分钟到达地点 1 在
- 道 2 经过时间 6 分钟到达地点 3 在
- 時刻 7 分钟到达地点 3 参加活动 参加 3 因为不能参加超过
3 个活动,所以答案是 2 。
入力例 2
1 0 2 1 1 1 100
出力例 2
2
由于不存在道路,从地点 1 无法移动,但在地点 1 举行了 2 可以参加某个活动。
入力例 3
5 8 10 1 2 149622151 1 4 177783960 4 5 118947237 1 3 33222944 1 5 295060863 3 5 110881471 2 3 34104208 3 4 273071547 2 650287940 4 839296263 3 462224593 1 492601449 4 384836991 1 191890310 5 576823355 3 782177068 3 404011431 1 818008580
出力例 3
6