测试数据来自 IkeLiu/1007

题目背景

家鸡是一个超级ikun。一天，他在网上发现他的偶像的演唱会将在n个城市举办。于是，他迅速动身去那些城市买票。（那些演唱会的时间不必在意，只需要关注票卖完的时间）。

题目描述

现在，给出城市数量n(从1到n，家鸡的家用0表示)，并给出家鸡的移动速度为每小时 \(a\) km（当然是开车），以及每场演唱会的举办城市和家鸡之间的路径数\(k\)（无向图）。第i场演唱会现在只剩了\(s_i\)张票，而每小时都会卖出\(t_i\)张票，家鸡希望能买到尽可能多的票。请输出他最多能去多少个城市买到票（在卖完时到达不算）

输入样例

第一行为两个整数，为n和k。
第2~k+1行，每行三个整数，分别是每条路径连接的两个城市代号和该路径的长度（km）。
第k+2~k+n+1行，每行两个整数，分别是\(s_i\)和\(t_i\)。
最后一行有一个实数，为\(a\)。

2 3
0 1 5
0 2 10
1 2 5
114514 114
1919810 191981
1

输出样例

一行，一个整数，为家鸡最多能去多少个城市买到票。

1

提示

1<=k,n<=1000,其余数皆在int范围内。