Birthday Gift

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

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

10

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

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