Lưu ý: Giới hạn thời gian của bài này là 2.5 giây.

Farmer John có \(N\) chồng kiện cỏ khô (\(1\leq N\leq 5\cdot 10^5\)), trong đó chồng thứ \(i\) chứa \(a_i\) kiện cỏ khô (\(1\leq a_i\leq 10^9\)). Ông muốn dọn hết các kiện cỏ này và có \(M\) con bò (\(1\leq M\leq 2500\)) sẵn sàng giúp đỡ. Nếu được thuê với chi phí \(c_i\) (\(1\leq c_i\leq 10^9\)), con bò thứ \(i\) sẽ lặp lại việc sau \(s_i\) lần (\(1\leq s_i\leq 100\)):

• Nếu chồng có ít nhất \(p_i\) kiện cỏ khô (\(1\leq p_i\leq 10^9\)), con bò sẽ lấy đi một kiện cỏ.
• Nếu chồng có ít hơn \(p_i\) kiện cỏ khô, con bò không làm gì cả.

Với mỗi chồng, FJ muốn lấy đi toàn bộ các kiện cỏ trong đó. Ông sẽ làm việc này bằng cách lần lượt thuê các con bò (có thể thuê cùng một con bò nhiều lần) cho đến khi chồng trở nên rỗng. Hãy giúp FJ xác định chi phí nhỏ nhất để dọn hết từng chồng.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\le T\le 100\)), là số bộ test độc lập. Mỗi bộ test có định dạng như sau:

Dòng đầu tiên chứa một số nguyên \(N\). Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\dots,a_N\).

Dòng thứ ba chứa một số nguyên \(M\). Mỗi dòng trong \(M\) dòng tiếp theo chứa \(p_i,s_i,c_i\).

Đảm bảo rằng các con bò có thể lấy đi toàn bộ kiện cỏ trong mọi chồng. Ngoài ra, đảm bảo rằng tổng \(N\) trên tất cả các bộ test không vượt quá \(5\cdot 10^5\), và tổng \(M\) trên tất cả các bộ test không vượt quá \(2500\).

Dữ liệu ra

Với mỗi bộ test, in ra \(N\) số nguyên cách nhau bởi dấu cách, trong đó số nguyên thứ \(i\) là chi phí để lấy đi toàn bộ kiện cỏ trong chồng thứ \(i\).

Ví dụ

2
3
15 100 10
4
101 1 1
1 4 8
9 3 5
15 2 3
3
15 100 10
4
101 1 1
1 1 5
9 1 8
15 1 3

29 155 21
73 328 50

Phân nhóm

• Inputs 2-3: \(a_i\le 100\).
• Inputs 4-5: \(\max(s)=1\).
• Inputs 6-9: \(\max(s)\le 4\).
• Inputs 10-15: \(\max(s)\le 20\).
• Inputs 16-21: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 US Open, Open Division — Haybale Stacks. Tác giả: Sujay Konda.
https://usaco.org/index.php?page=viewproblem2&cpid=1603