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

Input

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

Output

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

Input

3 2 4
1 2 100 5
2 3 100 1

Output

-1