Mô tả và yêu cầu

Có 𝑛 đồ vật đánh số từ 1 đến 𝑛. Đồ vật thứ 𝑖 có trọng lượng 𝑤𝑖 và giá trị 𝑐𝑖.
Có 𝑞 truy vấn, mỗi truy vấn gồm ba số nguyên 𝑙 , 𝑟 ,𝑊. Với mỗi truy vấn, chỉ được
phép lấy các số vật trong đoạn [𝑙, 𝑟] (mỗi đồ vật tối đa 1 lần) và tổng trọng lượng không
vượt quá 𝑊. Hỏi tổng giá trị lớn nhất có thể đạt được là bao nhiêu?
Yêu cầu: Hãy lập trình tính tổng giá trị lớn nhất có thể đạt được theo dữ kiện bài toán
trên.
Dữ liệu vào: Cho trong tệp tin văn bản RKS.INP gồm
 Dòng đầu tiên chứa số nguyên dương 𝑛 (1 ≤ 𝑛 ≤ 104);
 Dòng tiếp theo gồm 𝑛 dòng, dòng thứ 𝑖 chứa hai số nguyên dương 𝑤𝑖 và 𝑐𝑖
(1 ≤ 𝑤𝑖 ≤ 100, 𝑐𝑖 ≤ 104) – thông tin của đồ vât thứ 𝑖;
 Dòng tiếp theo chứa số nguyên dương 𝑞 (1 ≤ 𝑞 ≤ 105) – là số truy vấn;
 𝑞 dòng tiếp theo, mỗi dòng chứa ba số nguyên dương 𝑙 , 𝑟 , 𝑊 (1 ≤ 𝑙 ≤ 𝑟 ≤
𝑛, 1 ≤ 𝑊 ≤ 100);
Kết quả ra: Ghi ra tệp tin văn bản RKS.OUT gồm - Với mỗi truy vấn in ra môt dòng
là giá tri tối đa có thể đạt được cho truy vấn đó.

Ví dụ

RKS.INP                               RKS.OUT
                   4                                     35
                   2 15                                  60
                   2 20                                  4
                   4 36
                   1 4
                   3
                   1 2 4
                   1 4 7
                   3 4 2
Ràng buộc:
        Subtask 1: Có 40% số điểm tương ứng 40% số test với 𝑟                −  𝑙 ≤  100;
        Subtask 2: Có 30% số điểm tương ứng 30% số test với 𝑞                ≤  104;
        Subtask 3: Có 30% số điểm tương ứng 30% số test không ràng buộc gì thêm.