Thành phố Siruseri có một mạng lưới giao thông dày đặc, gồm giao điểm và con đường một chiều. Mỗi giao điểm được đặt một máy rút tiền tự động (ATM), hiện mỗi máy đang có số tiền . Ngoài ra, một vài giao điểm có các quán bar (sẽ giải thích sau).
Banditji đang dự tính một vụ trộm ngân hàng. Hắn sẽ xuất phát ở giao điểm , đi qua một số giao điểm theo mạng lưới giao thông trong thành phố, “viếng thăm” và rút hết tiền ở các máy ATM hắn đi qua. Hắn sẽ kết thúc cuộc chơi tại một trong các quán bar trước khi biến mất. Hắn có thể đi qua một giao điểm nhiều lần, nhưng dĩ nhiên, hắn chỉ có thể rút tiền tại lần đầu tiên “viếng thăm” máy ATM tại giao điểm đó.
Xác định số tiền tối đa mà Banditji có thể ăn trộm được. Dữ liệu đảm bảo hắn luôn có cách tẩu thoát về ít nhất một trong các quán bar.
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên dương và ;
dòng tiếp theo, mỗi dòng chứa hai số nguyên và chỉ ra một con đường một chiều từ đến ;
dòng tiếp theo, mỗi dòng chứa một số nguyên là số tiền hiện có trong máy ATM tại giao điểm ;
Dòng tiếp theo chứa hai số nguyên và lần lượt giao điểm mà Bandiji xuất phát và số lượng quán bar.
Dữ liệu ra:
In ra số tiền tối đa Banditji có thể ăn trộm được.
Mô tả test ví dụ. Banditji xuất phát tại thành phô . Hắn sẽ đi theo tuyến đường và lấy được tiền tại tất cả các giao điểm trừ giao điểm 6. Tổng số tiền là .
