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

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 $N$ cities numbered from $1$ to $N$. Snoopy lives in city $1$ and Reza lives in city $N$. There are $M$ bidirectional roads, the $i^{th}$ road is between the city $u_i$ and $v_i$ and $c_i$ is the cost of using this road. There is a weird rule in their country. For every road $i$, there is a restriction $k_i$, which means one can use the $i^{th}$ road carrying **at most** $k_i$ balloons. Initially, Snoopy has $C$ taka and $K$ balloons.

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

- The first line contains 4 space-separated integers $N$ $(2 \leq N \leq 10^{4})$, $M$ $(1 \leq M \leq 5\cdot10^{4})$, $C$ $(1 \leq C \leq 10^{9})$, $K$ $(1 \leq K \leq 10^{9})$ where $N$ denotes the number of cities, $M$ denotes the number of roads, $C$ and $K$ denotes the number of money and balloons Snoopy has respectively.
- Next $M$ lines contain $4$ space-separated integers $u$ $(1 \leq u \leq N)$, $v$ $(1 \leq v \leq N)$, $c$ $(1 \leq c \leq 10^{5})$, $k$ $(1 \leq k \leq 10^{9})$, means there is a road between the city $u$ and $v$ with cost $c$ and one can use this road carrying at most $k$ balloons.

Print the **maximum** number of balloons Snoopy can gift.

Input | Output |
---|---|

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. |

Input | Output |
---|---|

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. |

Input | Output |
---|---|

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. |

82% Solution Ratio

Fizzz_83Earliest,

Zihad_BdFastest, 0.0s

AUST_GriffinsLightest, 1.8 MB

Zobayer_AbedinShortest, 1096B

Login to submit

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