======================================
Trên
một mạng lưới giao thông có n nút, các nút được đánh số từ 1 đến n và giữa hai
nút bất kỳ có không quá một đường nối trực tiếp (đường nối trực tiếp là một
đường hai chiều). Ta gọi đường đi từ nút s đến nút t là một dãy các nút và các
đường nối trực tiếp có dạng:
s =
u1, e1, u2,..., ui, ei,
ui+1, ..., uk-1, ek-1, uk = t,
trong
đó u1, u2, …, uk là các nút trong mạng
lưới giao thông, ei là đường nối trực tiếp giữa nút ui và
ui+1(không có nút uj nào xuất hiện nhiều hơn một lần
trong dãy trên, j = 1, 2, …, k).
Biết
rằng mạng lưới giao thông được xét luôn có ít nhất một đường đi từ nút 1 đến
nút n.
Một
robot chứa đầy bình với w đơn vị năng lượng, cần đi từ trạm cứu hoả đặt tại nút
1 đến nơi xảy ra hoả hoạn ở nút n, trong thời gian ít nhất có thể. Thời gian và
chi phí năng lượng để robot đi trên đường nối trực tiếp từ nút i đến nút j
tương ứng là tij và cij (1 ≤ i, j ≤ n). Robot
chỉ có thể đi được trên đường nối trực tiếp từ nút i đến nút j nếu năng lượng
còn lại trong bình chứa không ít hơn cij (1 ≤ i, j ≤ n). Nếu
robot đi đến một nút có trạm tiếp năng lượng (một nút có thể có hoặc không có
trạm tiếp năng lượng) thì nó tự động được nạp đầy năng lượng vào bình chứa với
thời gian nạp coi như không đáng kể.
Yêu
cầu: Hãy xác định giá trị w nhỏ nhất để robot đ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 chứa một số nguyên dương n (2 ≤ n ≤ 500);
Dòng
thứ hai chứa n số, trong đó số thứ j bằng 1 hoặc 0 tương ứng ở nút j có hoặc
không có trạm tiếp năng lượng (j = 1, 2, …, n);
Dòng
thứ ba chứa số nguyên dương m (m ≤ 30000) là số đường nối trực tiếp có trong
mạng lưới giao thông;
Dòng
thứ k trong số m dòng tiếp theo chứa 4 số nguyên dương i, j, tij, cij (tij,
cij ≤ 10000) mô tả đường nối trực tiếp từ nút i đến nút j, thời
gian và chi phí năng lượng tương ứng.
Hai
số liên tiếp trên một dòng trong file dữ liệu cách nhau ít nhất một dấu cách.
Output
Ghi
ra số nguyên dương w tìm được.
Example
Input:
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
Output:
3