Problem
Có N thành phố trong cả nước, một số thành phố được nối với nhau bằng đường bộ. Phải mất một thùng xăng để lái xe trên một con đường. Ngoài ra, bạn có một hộp khí chứa cùng một lượng nhiên liệu như một bình xăng.
Ở mỗi thành phố, một bình xăng có giá khác nhau. Bạn cần đi từ thành phố đầu tiên đến thành phố thứ N, tiêu càng ít tiền càng tốt.
Ở mỗi thành phố, bạn có thể đổ đầy bình, đổ đầy bình và bình hoặc đổ xăng từ bình vào bình. Điều này cho phép bạn tiết kiệm tiền bằng cách mua xăng ở những thành phố rẻ hơn, nhưng hộp xăng chỉ đủ đổ đầy một bình!
Đầu vào
Dòng đầu tiên chứa số N (1<=N<=100), dòng tiếp theo chứa N số, số thứ i xác định chi phí xăng của thành phố thứ i (tất cả đều là số nguyên từ phạm vi từ 0 đến 100). Sau đó là số M – số lượng đường trong nước, tiếp theo là mô tả về chính những con đường đó. Mỗi đường được cho bởi hai số – số lượng các thành phố mà nó kết nối. Tất cả các con đường đều là hai chiều (nghĩa là chúng có thể được lái theo cả hướng này và hướng khác), luôn không có nhiều hơn một con đường giữa hai thành phố, không có con đường nào dẫn từ thành phố đến chính nó.
Đầu ra
Bắt buộc phải xuất một số duy nhất – tổng chi phí của tuyến đường hoặc -1 nếu không thể đến đó.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
4
1 10 2 15
4
1 2
1 3
4 2
4 3
|
2 |