# Practice on Toph

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

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

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.

### Statistics

82% Solution Ratio

Fizzz_83Earliest, Jul '20