Nâng cấp đường

View as PDF

Submit solution

All submissions

Best submissions

Points: 0.50 (partial)

Time limit: 1.0s

Memory limit: 256M

Input: stdin

Output: stdout

Problem source:

TST_CSP_2022

Problem type

Allowed languages

C, C++, Java, ~~Kotlin~~, Pascal, ~~PyPy~~, Python, Scratch

Đất nước Byteland xinh đẹp có ~n~ thành phố được đánh số từ ~1~ đến ~n~. Các thành phố được kết nối bởi ~m~ con đường hai chiều (được đánh số từ ~1~ đến ~m~ ). Con đường thứ ~i~ kết nối hai thành phố ~u_{i}~ và ~v_{i}~, con đường này được đánh giá có điểm an toàn là ~w_{i}~. Giao thông đảm bảo rằng từ một thành phố có thể đến bất kì thành phố nào khác qua các con đường đã cho.

Để phát triển đất nước, chính quyền giao cho Bộ giao thông đưa ra phương án chọn ~n-1~ con đường trong số ~m~ con đường trên làm đường quốc lộ, sao cho tính liên thông giữa các thành phố vẫn được đảm bảo. Bộ trưởng yêu cầu đưa ra phương án chọn con đường sao cho tổng độ an toàn cho ~n-1~ con đường này là lớn nhất có thể.

Mỗi một năm nhà nước sẽ cho phép nâng cấp một con đường quốc lộ. Quá trình này diễn ra trong ~Q~ năm. Ở năm thứ ~i~, sau khi nâng cấp con đường ~t_{i}~ thì điểm an toàn của con đường này được nâng thêm ~x_{i}~. Tức là, nếu điểm an toàn của con đường trước khi nâng cấp là ~w~, thì sau khi nâng cấp, độ an toàn của con đường này sẽ là ~w+x_{i}~. Biết rằng, theo thang điểm đánh giá, mức độ an toàn của mỗi con đường được đánh giá theo thang điểm ~k~. Tức là, ~w+x_{i} \leq k~ với ~k~ được quy định từ trước.

Sau mỗi năm, bạn hãy tính tổng điểm an toàn của phương án chọn ~n-1~ con đường làm quốc lộ (sau khi thực hiện nâng cấp đường) sao cho tổng điểm an toàn là lớn nhất có thể.

Dữ liệu:

Dòng đầu tiên là 3 số nguyên dương ~n, m, \mathrm{k}\left(1 \leq n \leq m \leq 10^{5}, 1 \leq \mathrm{k} \leq 500\right)~;
~m~ dòng tiếp theo, dòng thứ ~i~ gồm 3 số ~u_{i}, v_{i}, w_{i}\left(1 \leq w_{i} \leq \mathrm{k}\right)~;
Dòng tiếp theo là số ~Q\left(1 \leq Q \leq 10^{5}\right)~;
~Q~ dòng tiếp theo, dòng thứ ~i~ gồm hai số ~t_{i}~ và ~x_{i}\left(x_{i}>0\right)~. Đề đảm bảo tổng điểm an toàn của con đường ~t_{i}~ sau khi nâng cấp không vượt quá ~k~.

Kết quả:

Ghi ra ~Q~ dòng, dòng thứ ~i~ là tổng điểm an toàn của ~n-1~ con đường được chọn làm quốc lộ sau khi thực hiện việc nâng cấp đường của năm thứ ~i~.

Ví dụ:

Sample Input

Sample Output