Bedao OI Contest 2 - Câu cá
Xem dạng PDF
Trung rất thích câu cá. Hôm nay cậu đi câu cá ở điểm câu bên hồ có ~n~ con cá, con cá thứ ~i~ có cân nặng ~w_i~, cách vị trí câu ~d_i~ mét, và khi bán con cá này, ta thu được một khoảng tiền là ~a_i~.
Tiệm đồ câu có ~m~ loại cần câu, loại cần thứ ~i~ chịu được cân nặng tối đa ~x_i~ và có giá ~c_i~. Dây cước có giá ~b~ đồng cho mỗi mét dây cước. Để câu được con cá thứ ~i~, cần câu Trung mua phải chịu được cân nặng của con cá (~x \geq w_i~) và độ dài dây cước không được nhỏ hơn khoảng cách của con cá thứ ~i~ tới điểm câu. Một cần câu có thể được sử dụng lại nhiều lần.
Yêu cầu: Tính số tiền lời tối đa của Trung sau chuyến đi câu.
Input
Vào từ file văn bản fishing.inp:
Dòng đầu chứa một số nguyên dương ~n~, số lượng cá trong hồ ~(1 \leq n \leq 2\cdot10^5)~.
Dòng thứ ~i~ trong ~n~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương ~w_i, d_i, a_i~, lần lượt là cân nặng, khoảng cách tới vị trí câu và giá trị của con cá thứ ~i~ ~(1 \leq w_i, d_i, a_i \leq 10^9)~.
Dòng tiếp theo gồm số nguyên dương ~m~, số lượng cần câu ở tiệm đồ ~(1 \leq m \leq 2\cdot10^5)~.
Dòng thứ ~i~ trong ~m~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương ~x_i, c_i~, lần lượt là cân nặng tối đa cần chịu được và giá của cần câu thứ ~i~ ~(1 \leq x_i, c_i \leq 10^9)~.
Dòng cuối chứa số nguyên ~b~, giá tiền của mỗi mét dây câu ~(1 \leq b \leq 10^9)~.
Output
Đưa ra file văn bản fishing.out một số nguyên duy nhất là lợi nhận tối đa của Trung sau chuyến đi
câu.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~50\%~ | ~m~, ~n~, ~d_i \leq 10^3~ |
| 2 | ~50\%~ | Không có điều kiện gì thêm |
Sample Input 1
3
4 3 10
2 5 4
1 2 1
3
6 100
2 7
4 3
1
Sample Output 1
7
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
chuc moi nguoi lam bai vui ve :3, nhieu thanh cong trong cuoc song nha ;>>.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.