Mạng lưới giao thông gồm ~n~ nút, giữa một số nút có đường nối 2 chiều. Đoạn đường chứa 2 thông tin, ~t[i,j]~ là thời gian đi đoạn đường, ~c[i,j]~ là năng lượng để đi hết đoạn đường. Người máy chỉ đi qua được một đoạn đường ~(i,j)~ khi năng lượng còn lại trong bình không ít hơn ~c[i,j]~. Trên một số nút có trạm tiếp năng lượng, khi người máy đến nút này thì được nạp đầy năng lượng. Thời gian nạp năng lượng coi như không đáng kể. Người máy xuất phát tại nút 1 với bình năng lượng ~w~ đến cứu hỏa tại nút ~n~.

Yêu cầu: Xác định giá trị ~w~ nhỏ nhất để người máy đi được trên một đường đi từ nút 1 đến nút ~n~ trong thời gian ít nhất.

Input

• Dòng đầu tiên ghi số nguyên dương ~N~ (~2 \le N \le 500~).
• Dòng thứ hai ghi ~N~ số 1 hoặc 0 thể hiện ở trạm thứ ~i~ có hoặc không có trạm tiếp năng lượng.
• Dòng thứ ba ghi ~M~ là số tuyến đường (~M \le 30000~).
• Dòng thứ ~k~ trong ~M~ dòng tiếp ghi thông tin về một tuyến đường gồm 4 số ~i, j, t[i,j], c[i,j]~ (~t[i,j], c[i,j] \le 10^4~).

Output

• Ghi ra số ~w~ tìm được.

Sample Input 1

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

Sample Output 1

3