Description

  大明被一个神秘人奉命控制前去摧毁他的敌人的“Military storehouse”，不过，不幸的是，你被敌军关到了真空监狱，于是，你用万能钥匙开了牢门。只不过，你身上剩余的氧气不多了，你必须前去监狱里的氧气点补充氧气！
  已知有n（n≤3000）个氧气点，编号为１到ｎ，你所在的地方编号为０，但是，监狱里有一个超级牛逼的机器人，叫“JEVER FIGHTING ZJJ's KILLER”，躲在n＋１点

  这个机器人不会抓躲在牢房里的人（但它可以路过牢房），但一旦有人逃出，他就可以获取这个人策划的路线，并且由此策划出最佳的抓捕路线（简单来说就是获取出大明在每个点的时间与路线，然后推出跑去哪个点能够抓住大明，或者跑到哪个点可以使大明和机器人的距离最短）！
  由于一秒你要呼吸ｍ格单位的空气，而你一开始只有ｔ格单位的空气，每个点与每个点都有可能有真空通道！每个真空通道你或机器人都要ki秒才可以通过（你和机器人速度相同），每个点可以获得ui格单位的空气，但是每个点一次停留太久会喷出不干净的氧气，所以，一个点一次最多停留pi秒。
  由于机器人的BUG能力，你没法与机器人兜圈圈，于是你必须规划一条最优方案，你想清楚自己出去回来后的剩余最大空气有多少（当然，不出去就是ｔ啦！且你只能出去一次，不能多次回来再出去，但可以路过）？
  不过，当机器人离你的距离不超过一秒就可以到达时，你就等于被抓了！（当你的氧气为0，你就扑街了！）

Input Format

输入三个整数，n，t，m，bian（bian 代表有多少条真空通道，无重边）
接下来 bian 行，每行三个整数，xi，yi，ki，表示编号为 xi 和 yi 的两个点有一条真空通道，要花 ki 秒通过
接下来n行，每行两个整数，u_i 、p_i，表示编号为i的氧气点的每秒可以所获氧气和最多呆多少秒
注：0和n+1点没有真空管道

Output Format

一个整数，最大氧气！

4 10 2 8
0 1 2
0 2 1
2 5 5
1 3 2
2 4 2
3 2 3
0 4 2
3 5 5
50 10
1 10
1 10
1 10

52

Hint

这道题是一道较水的最短路，你只要以机器人到每个点的最短时间为点限制就可以了！
样例解释：机器人：5->2->0花6秒到达0点，则大明要想在机器人到达之前躲在牢房里，他必须在6-1=5秒钟内到达，最大就是0->1（等待一秒）->0所获得的52格单位的氧气！
对于40%的样例
n≤200,bian≤1000,k_i≤10,u_i≤30,p_i≤50,t≤100,m≤5
对于60%的样例
n≤2000,bian≤20000,k_i≤20,u_i≤50,p_i≤100,t≤500,m≤15
对于100%的样例
n≤4000,bian≤100000,k_i≤40,u_i≤70,p_i≤300,t≤1000,m≤30

Source

by zhangjianjunab