There are N nodes labelled 1 to N and M cables (1 to M) in a network where each cable is bidirectional. Each cable between nodes Ui and Vi has an energy Ei and time Ti associated with it. The packet has an initial energy X and starts at node 1. When a packet passes through the cable, its energy is attenuated by Ei and time taken is Ti. The packet cannot travel through a cable if it doesn't have sufficient energy. Each of the nodes has infinite energy boosters where at each node Vi, it takes time Pi to boost the energy of packet by Bi. Find the minimum time taken by the packet to reach to each of the nodes 2 to N starting from node 1.

Input:

First line contains 3 values N, M & X.
Each of the next M lines contain 4 values Ui, Vi, Ei and Ti.
Each of the next N lines containes 2 values Bi and Pi.

Output:

Print the minimum time taken by the packet to reach each of the nodes 2 to N starting from node 1.

Sample input -

3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5

Output -

2
14

Explanation -
For destination node 2, the packet travels through the cable 1-2 and time taken is 2

For destination node 3, the packet first travels from 1 to 2 and time taken is 2. //packet energy = 0
It then gets 3 packets of energy boosters(each packet is given as 1 unit) at node 2 and time taken is 6. //packet energy = 3.
It then travels back to 1 from node 2 and time taken is 2 units. //packet energy = 3 - 1 = 2
It then reaches to 3 from 1 and time taken = 4 //packet energy = 2 - 2 = 0
Total time = 2+6+2+4 = 14

P.S: The energy boosters cannot be used partially meaning if the energy booster is having value Bi and time taken is Pi, then partial amount of Bi cannot be used. It can be assumed that these energy boosters are like packets - we can fully use them or cannot.

If you get the intuition behind the solution, please post it in the comments. Thanks in advance!