在游遍神秘岛过程中，Z4发现每一个小岛上都有若干个奇怪的类似小水缸似的立方体，这另到Z4相当迷惑不解！这天晚上，忽然下起了一场大雨，在中心岛小树屋上类似那个圆形石槽中间的小孔中涌出了一泓清水，z4不禁一阵欢呼也不自觉的联想起那些类似小水缸的东西。
经过一连数日的观察，发现那些形似小水缸是用来收集雨水的集水器，连同有很多埋在地底下的贮水器形成一个庞大的供水系统。而且特别的是这个供水网络不存在循环连接，也就是贮水系统的连接不存在环。
供水系统是用粗幼不同的水管连接，所有水管都是单向传输的。所有的集水器都有且仅有一条指向某个贮水器的输出水管。所有的贮水器都连有若干条或自某集水器连至或自其他贮水器连至的输入水管，也有且仅有一条连向其他贮水器的输出水管。在小树屋地底下有一个中央贮水器，类似于其他贮水器，所有收集到的雨水将最终汇集到这里，它的输出水管直接供应上树屋。
这套供水系统是这样工作的：下雨过后，每个集水器都收集到一定体积的水，并通过水管，贮水器向中央贮水器汇集。而当任意一个贮水器所有输入水管都输送完毕，他的输出水管才会开启，把当中所有的水输送出去。直到中央贮水器的出水水管开启时，树屋上的Z4（可怜的Z4！）才得到水供应。
由于严密的设计，所有贮水器的容量都是足够的大！
由于水管粗幼不同，所以每道水管运水的速度各不相同。
现在问题是，当雨停后过多久，中央贮水器才会向树屋上供水？智慧过人的Z4当然不会给自己计算找麻烦，所有数据中的时间单位统一为s，体积单位统一为L。

输入文件water.in的第一行包括四个整数n,m,s_rain,t_rain(1<=n<=1000,1<=m<=1000000)分别表示n个贮水器，m个集水器，了方便计算，Z4人为地把他们分别按1..n,1..m标号，而其中第n个贮水器即为中央贮水器，s_rain表示单位时间里单位面积的降雨量，t_rain表示该次降雨持续时间。
接下来的m行分别描述第1至第m个集水器。每行含有四个整数S,h,k,t。S表示该集水器容器底面积，h表示容器的高（S*h<=20000），k表示该集水器输出水管指向第k个贮水器，t表示输出水管输送一单位的水所用的时间。
再接下来n-1行分别描述第1至第n-1个贮水器。每行包括两个整数k,t。k表示该贮水器输出水管指向第k个贮水器，t表示该贮水器的输出水管输送一单位的水所用的时间。

输出文件water.out只有一行，表示雨停后直到得到水供应的时间.(结果肯定<=maxlongint)

5 5 1 1
10 1 1 2
5 1 3 4
10 1 4 3
10 1 4 6
8 1 5 9
2 2
5 1
5 2
5 2

100