Như đã biết, giáo sư Y đã đầu tư các mảnh vườn trồng cây ăn quả để phục vụ cho các bữa tiệc mừng sau khi tổ chức các kỳ CSLPreVNOI, tuy nhiên, do đầu tư rất nhiều vườn cây nên quả thu hoạch dùng không hết, giáo sư có dự định bán cho các lái buôn hoa quả.
Giáo sư có vườn cây được đánh số từ đến . Giữa các vườn cây có con đường một chiều đánh số từ đến , con đường thứ giáo sư sẽ thu số tiền mỗi khi một lái buôn đi qua con đường này để đến các vườn cây mua quả, giữa hai vườn cây chỉ có không quá một con đường một chiều và có một vườn cây có thể đi đến được tất cả các vườn cây khác thông qua các con đường một chiều này. Có một số lái buôn đến xin mua quả từ các vườn cây của giáo sư. Lái buôn được cho bởi hai số là chỉ số vườn cây mà họ xuất hiện và là số tiền mà họ sẽ bỏ ra để được mua quả ở một vườn cây nào đó (mới chỉ là phí đàm phán thôi). Vườn cây thứ khi đến mùa thu hoạch được giáo sư định giá là số tiền mà lái buôn sẽ phải trả để mua (tất cả) quả ở vườn cây này. Như vậy, nếu lái buôn đến ở vườn cây mà muốn mua quả ở vườn cây thì phải có đường đi từ đến và sẽ phải trả cho giáo sư số tiền là , trong đó là tổng chi phí phải trả trên con đường đi từ đến .
Lưu ý: Mỗi lái buôn khi đến mua quả sẽ mua toàn bộ quả của đúng một mảnh vườn (tất nhiên phải có đường tới mảnh vườn đó) và mỗi một mảnh vườn cũng chỉ bán cho đúng một lái buôn (tất nhiên là chỉ khi được thu hoạch). Một đoạn đường có thể cho nhiều lái buôn đi qua.
Có sự kiện xảy ra thuộc một trong hai loại:
: cho biết có một lái buôn đến mảnh vườn và trả chi phí để "đàm phán" mua quả ở một mảnh vườn
: cho biết có mảnh vườn được thu hoạch với giá trị là
Giáo sư nhờ các bạn tính giúp: Sau mỗi sự kiện, nếu lựa chọn một cách hợp lý việc bán quả ở các mảnh vườn cho các lái buôn thì giáo sư thu được số tiền tối đa là bao nhiêu?
(Chú ý là không cần phải bán cho mọi lái buôn)
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên dương và là số mảnh vườn và số sự kiện xảy ra;
dòng tiếp theo, dòng thứ chứa ba số nguyên cho biết có con đường một chiều đi từ mảnh vườn tới mảnh vườn với mức phí đi qua là ;
dòng tiếp theo, mỗi dòng chứa ba số mô tả một sự kiện .
Dữ liệu ra:
Ghi ra dòng là kết quả sau mỗi sự kiện xảy ra (theo đúng thứ tự).
Giới hạn:
Trong tất cả các test có , chi phí để đi qua các con đường là số nguyên dương không quá , phí đàm phán của các lái buôn và giá trị của các mảnh vườn là số nguyên dương không quá . Trong đó:
Test #
Điểm
Ràng buộc bổ sung
1
4
C2
2
3,4
8
5 ~ 10
24
C1
11 ~ 13
12
C2
14,15
8
A1
16,17
B1
18,19
C1
20 ~ 24
20
C2
25
4
Ý nghĩa các ràng buộc bổ sung:
A: Con đường thứ đi từ mảnh vườn thứ đến mảnh vườn thứ
B: con đường thứ đi từ mảnh vườn thứ đến mảnh vườn thứ
C: Không có ràng buộc thêm về cấu trúc các mảnh vườn và các con đường
1: Tất cả các sự kiện loại xảy ra sau các sự kiện loại
2: Không có ràng buộc thêm về các sự kiện
Ví dụ (Tải test đề bài và 2 test mẫu khác ở "Tệp đính kèm" phía trên đề bài):
Sau sự kiện thứ nhất: chưa có vườn cây nào được thu hoạch nên kết quả là
Sau sự kiện thứ hai: Có một lái buôn ở vườn thứ thu hoạch luôn vườn cây này (cách duy nhất), kết quả thu được là
Sau sự kiện thứ ba và thứ tư có thêm hai lái buôn ở vườn cây số và số nhưng phương án tốt nhất vẫn là cho lái buôn ở vườn cây số thu hoạch vườn cây thứ nên kết quả vẫn là
Sau sự kiện thứ năm: có phương án:
Một là cho lái buôn ở vườn số thu hoạch vườn số : số tiền thu được là
Hai là cho lái buôn ở vườn số thu hoạch vườn số và lái buôn ở vườn số thu hoạch vườn số , số tiền thu được là:
Do đó: sau sự kiện thứ năm, kết quả là
