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.