Đất nước ABC có \(n\) thành phố và \(m\) con đường một chiều. Con đường thứ \(i\) nối hai thành phố \(u_i\) và \(v_i\) với nhau, có độ dài \(l_i\) và có chi phí \(t_i\).

\(H\) là một du khách. Hiện tại, anh đang ở thành phố \(1\) và cần đi tới thành phố \(n\). Tuy nhiên anh ta chỉ mang đúng \(K\) đồng tiền.

Hãy giúp \(H\) tính toán lộ trình ngắn nhất từ thành phố \(1\) tới \(n\) mà chỉ mất tổng chi phí ít hơn hoặc bằng \(K\).

Input

• Dòng thứ nhất chứa \(2\) số nguyên dương \(n, m\).
• Dòng thứ hai chứa số nguyên dương \(K\).
• \(m\) dòng sau mỗi dòng gồm \(4\) số nguyên dương \(u_i, v_i, l_i, t_i\) \((1 \le u, v \le n, u \neq v)\), miêu tả con đường nối thành phố \(u_i\) với \(v_i\) có độ dài \(l_i\) và chi phí \(t_i\).

Output

• In ra độ dài đường đi ngắn nhất từ \(1\) tới \(n\) mà tổng chi phí không quá \(K\).
• Nếu không có lộ trình nào để đi từ \(1\) tới \(n\) và tiêu không quá \(K\), in ra \(-1\).

Constraints

• \(1 \le n \le 100\).
• \(1 \le m \le 1000\).
• \(1 \le k \le 10000\).
• \(1 \le l_i \le 1000\).
• \(0 \le t_i \le 1000\).

Subtasks

• Subtask \(1\): \(1 \le n,m \le 20\) (30%)
• Subtask \(2\): Không có ràng buộc gì thêm (70%)

Sample Input 1

6 7
5
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2

Sample Output 1

11

Explanation 1

Đi theo lộ trình \((1,3,5,4,6)\).

Sample Input 2

4
4
0
1 4 5 2
1 2 1 0
2 3 1 1
3 4 1 0

Sample Output 2

-1

Explanation 2

Không có lộ trình nào để đi từ \(1\) tới \(4\) tiêu không quá \(0\).