Charged Courier

A courier must travel through a network of cities from city $1$ to city $N$. Each road can only be used in its listed direction, gives a certain delivery reward, and consumes some amount of battery.

The courier starts with at most $B$ battery units and cannot spend more than $B$ battery units over the whole trip. Determine the maximum total reward the courier can collect while reaching city $N$. If it is impossible to reach city $N$, output -1.

Input

The first line contains three integers $N$, $M$, and $B$: the number of cities, the number of roads, and the maximum battery that may be spent.

Each of the next $M$ lines contains four integers $u_i$, $v_i$, $r_i$, and $c_i$, describing a directed road from city $u_i$ to city $v_i$ with reward $r_i$ and battery cost $c_i$.

Output

Output one integer: the maximum reward possible while reaching city $N$ using at most $B$ battery units, or -1 if city $N$ cannot be reached.

Constraints

• $2 \le N \le 500$
• $0 \le M \le 5000$
• $0 \le B \le 3000$
• $1 \le u_i, v_i \le N$
• $u_i \ne v_i$
• $0 \le r_i \le 10^9$
• $1 \le c_i \le 3020$

Example 1

4 5 7
1 2 10 3
2 4 20 4
1 3 25 5
3 4 10 3
2 3 15 2

30

Explanation

The courier can travel from city $1$ to city $2$ to city $4$, spending $3 + 4 = 7$ battery and collecting $10 + 20 = 30$ reward. The route through city $3$ from city $1$ would collect more reward, but it spends too much battery.

Example 2

3 2 4
1 2 100 5
2 3 100 1

-1