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.
Input
- 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.
Output
Print the maximum number of balloons Snoopy can gift.
Samples
| 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. | |
