Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Birthday Gift

By yead_025 · Limits 1s, 512 MB

Snoopy and Reza are best friends and today is Reza's birthday. Now Snoopy wants to join Reza's birthday celebration and gift him some balloons. In their country, there are NN cities numbered from 11 to NN. Snoopy lives in city 11 and Reza lives in city NN. There are MM bidirectional roads, the ithi^{th} road is between the city uiu_i and viv_i and cic_i is the cost of using this road. There is a weird rule in their country. For every road ii, there is a restriction kik_i, which means one can use the ithi^{th} road carrying at most kik_i balloons. Initially, Snoopy has CC taka and KK balloons.

Now Snoopy wants to know what is the maximum number of balloons he can gift Reza. For this he wants your help.

Input

  • The first line contains 4 space-separated integers NN (2N104)(2 \leq N \leq 10^{4}), MM (1M5104)(1 \leq M \leq 5\cdot10^{4}), CC (1C109)(1 \leq C \leq 10^{9}), KK (1K109)(1 \leq K \leq 10^{9}) where NN denotes the number of cities, MM denotes the number of roads, CC and KK denotes the number of money and balloons Snoopy has respectively.
  • Next MM lines contain 44 space-separated integers uu (1uN)(1 \leq u \leq N), vv (1vN)(1 \leq v \leq N), cc (1c105)(1 \leq c \leq 10^{5}), kk (1k109)(1 \leq k \leq 10^{9}), means there is a road between the city uu and vv with cost cc and one can use this road carrying at most kk balloons.

Output

Print the maximum number of balloons Snoopy can gift.

Samples

InputOutput
5 4 9 15
1 2 3 10
1 4 10 12
2 5 4 12
4 5 9 15
10

Snoopy can choose the path 1->2->5 which costs 7 and he can gift 10 balloons.

InputOutput
5 5 15 15
1 3 4 12
1 4 3 10
4 2 8 10
3 2 16 12
2 5 4 12
10

Snoppy can choose the path 1->4->2->5 which costs 15 and he can gift 10 balloons.

InputOutput
6 6 20 7
1 2 1 20
2 3 1 20
3 4 1 30
3 5 1 10
4 6 1 3
5 6 2 5
5

Snoppy can choose the path 1->2->3->5->6 which costs 5 and he can gift 5 balloons.


Discussion

Statistics


82% Solution Ratio

Fizzz_83Earliest, Jul '20

Zihad_BdFastest, 0.0s

AUST_GriffinsLightest, 1.8 MB

Zobayer_AbedinShortest, 1096B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.