Ở một nơi rất xa có một quần đảo gồm có hòn đảo được đánh số từ \(1\) đến \(n\). Có \(m\) tuyến đường biển để đi lại hai chiều giữa các đảo, tuyến đường thứ \(i\) nối hai đảo khác nhau \(u_i\), \(v_i\ (1\leq u_i,\ v_i\leq n)\) và mất \(t_i\) đơn vị thời gian để đi hết nó.

Để đi lại giữa các đảo, chúng ta sử dụng tàu thủy có độ dày thân tàu là \(k\) cm. Mỗi khi tàu đi hết tuyến đường \(i\), thân tàu bị làm mòn \(h_i\) cm. Như vậy, để đi từ đảo \(A\) đến đảo \(B\) với tàu thủy có độ dày thân tàu là \(k\) cm bằng các tuyến đường thì tổng độ làm mòn thân tàu trên các tuyến đường mà nó đi qua phải nhỏ hơn \(k\).

Yêu cầu: cho trước hai hòn đảo \(A\) và \(B\ (1\leq A,\ B\leq n,\ A\neq B)\). Tìm đường đi cho con tàu khi đi từ đảo \(A\) tới đảo \(B\) có tổng thời gian là ít nhất (thỏa mãn có tổng độ làm mòn thân tàu khi đi trên đường đi này nhỏ hơn \(k\)).

Input

• Dòng thứ nhất gồm \(3\) số nguyên \(k,\ n,\ m\ (1\leq k\leq200,\ 2\leq n\leq10^4,\ m\leq10^5)\), mỗi số cách nhau một dấu cách;
• Dòng thứ \(i\) trong \(m\) dòng tiếp theo, mỗi dòng chứa \(4\) số nguyên \(u_i,\ v_i,\ t_i,\ h_i\ (1\leq u_i,\ v_i\leq n,\ u_i\neq v_i,\ 1\leq t_i\leq10^5,\ 0\leq h_i\leq200)\) thể hiện đi lại trên tuyến đường thứ \(i\) nối hai đảo \(u_i,\ v_i\) mất \(t_i\) đơn vị thời gian và độ làm mòn thân tàu khi đi trên nó là \(h_i\), mỗi số cách nhau một dấu cách;
• Dòng cuối cùng chứa hai số nguyên \(A\) và \(B\ (1\leq A,\ B\leq n,\ A\neq B)\).

Output

• In ra một số nguyên duy nhất là tổng thời gian ít nhất khi đi từ đảo \(A\) tới đảo \(B\) thỏa mãn yêu cầu trên, hoặc đưa ra \(-1\) nếu không có cách nào đi từ đảo \(A\) tới đảo \(B\).

Ví dụ

Sample input

10 4 7
1 2 4 4
1 3 7 2
3 1 8 1
3 2 2 2
4 2 1 6
3 4 1 1
1 4 6 12
1 4

Sample output

7

Ràng buộc

• Có \(50\%\) số test tương ứng \(50\%\) số điểm có \(k=1,\ n\leq2000\);
• Có \(25\%\) số test tương ứng \(25\%\) số điểm có \(n\leq2000\);
• Có \(25\%\) số test tương ứng \(25\%\) số điểm có \(n\leq10^4\).