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.