Tất cả các đường trong thành phố của Siruseri đều là một chiều. Theo luật của quốc gia này, tại mỗi giao lộ phải có một máy ATM. Điều đáng ngạc nhiên là các cửa hàng chơi điện tử cũng nằm ở các giao lộ, tuy nhiên, không phải tại giao lộ nào cũng có cửa hàng chơi điện tử.
Banditji là một tên trộm nổi tiếng. Hắn quyết định làm một vụ động trời: khoắng sạch tiền trong các máy ATM trên đường đi, sau đó ghé vào một cửa hàng chơi điện tử để thư giản. Nhờ có mạng lưới thông tin rộng rãi, Banditji biết được số tiền có ở mỗi máy ATM ngày hôm đó. Xuất phát từ trung tâm, tên trộm lái xe đi dọc theo các phố, vét sạch tiền ở các ATM gặp trên đường đi. Banditji có thể đi lại nhiều lần trên một số đoạn phố, nhưng sẽ không thu gì được thêm từ các ATM đã bị khoắng trước đó. Lộ trình của Banditji phải kết thúc ở giao lộ có cửa hàng chơi điện tử. Banditji biết cách vạch lộ trình để tổng số tiền trộm được là lớn nhất.
Ở ví dụ nêu trên hình vẽ, thành phố có giao lộ đánh số từ đến , số tiền trong ATM được ghi ở bên cạnh nút. Các nút hình sao chỉ giao lộ có cửa hàng chơi điện tử. Đường chấm chấm cho biết lộ trình của tên trộm. Tổng cộng, hắn đã lấy được đồng.
Yêu cầu: Cho biết – số giao lộ, – số đoạn đường nối hai giao lộ, – số giao lộ có cửa hàng chơi điện tử và các nơi có cửa hàng, – số tiền trong ATM đặt ở giao lộ , – giao lộ trung tâm. Hãy xác định tổng số lượng tiền bị trộm .
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên và ;
Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và xác định đường đi từ giao lộ tới giao lộ ;
Dòng thứ trong dòng tiếp theo chứa số nguyên ;
Dòng thứ chứa hai số nguyên và ;
Dòng cuối cùng chứa số nguyên xác định các giao lộ có cửa hàng chơi điện tử.
