Đường phố trong thành phố Siruseri đều là đường một chiều. Các con đường nối giữa các giao lộ. Theo quy định pháp luật, tại mỗi giao lộ đều đặt một máy rút tiền ATM của ngân hàng Siruseri. Một điều kỳ lạ là các quán bar ở Siruseri cũng đều nằm tại các giao lộ, mặc dù không phải giao lộ nào cũng có quán bar.
Banditji lên kế hoạch thực hiện vụ cướp ATM chấn động nhất lịch sử Siruseri. Hắn sẽ xuất phát từ trung tâm thành phố, đi dọc theo các con đường một chiều, cướp tất cả các máy ATM mà hắn đi qua, và cuối cùng sẽ ăn mừng chiến thắng tại một quán bar.
Sử dụng kỹ thuật hacker cao siêu, hắn biết được số tiền mặt có thể cướp được tại mỗi máy ATM. Hắn muốn bạn giúp tính toán tổng số tiền mặt nhiều nhất có thể cướp được khi xuất phát từ trung tâm và kết thúc tại một quán bar nào đó. Hắn có thể đi qua cùng một giao lộ hoặc con đường nhiều lần. Tuy nhiên, một khi đã cướp một máy ATM, máy đó sẽ không còn tiền nữa.
Ví dụ, giả sử thành phố có giao lộ, tình hình kết nối đường đi như hình dưới đây:
Trung tâm thành phố ở giao lộ (được đánh dấu bằng mũi tên ), các giao lộ có quán bar được ký hiệu bằng vòng tròn đôi. Số tiền trong mỗi ATM được ghi phía trên giao lộ. Trong ví dụ này, tổng số tiền Banditji có thể cướp là , với lộ trình cướp: .
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên . là số giao lộ, là số con đường.
dòng tiếp theo, mỗi dòng chứa hai số nguyên trong khoảng đến . Hai số ở dòng thứ biểu thị điểm bắt đầu và điểm kết thúc của con đường thứ .
dòng tiếp theo, mỗi dòng một số nguyên, lần lượt biểu thị số tiền trong ATM tại mỗi giao lộ.
Dòng tiếp theo chứa hai số nguyên . là mã số trung tâm thành phố (điểm xuất phát). là số lượng quán bar.
Dòng tiếp theo chứa số nguyên, là mã số các giao lộ có quán bar.
Kết quả:
Xuất một số nguyên, biểu thị tổng số tiền mặt lớn nhất Banditji có thể cướp được từ trung tâm đến khi kết thúc tại một quán bar.
