Vụ trộm thế kỷ

Bức thư từ Kid đã được gửi đến và vụ trộm thế kỷ tại thành phố Beika sắp bắt đầu. Nội dung bức thư ghi rằng có tổng cộng ~N~ địa điểm bị nhắm đến. Thanh tra Nakamori và các cộng sự phải tìm cách di dời các bảo vật quý hiếm ở các địa điểm này. Ở mỗi địa điểm thứ ~i~, bảo vật có trọng lượng ~W_i~ và mang giá trị ~V_i~.

Tuy nhiên, sở cảnh sát vừa đưa ra danh sách gồm ~Q~ kế hoạch, mỗi kế hoạch ~j~ yêu cầu chỉ được di dời các bảo vật nằm ở các địa điểm trong khoảng từ ~L_j~ đến ~R_j~, đồng thời do vấn đề vận chuyển nên tổng trọng lượng các bảo vật không được vượt quá ~Z_j~.

Bạn hãy giúp thanh tra Nakamori tính toán rằng với mỗi kế hoạch, tổng giá trị lớn nhất các bảo vật có thể di dời là bao nhiêu.

Input

• Dòng đầu tiên chứa số nguyên ~N~ (~1 \le N \le 2.10^4~).
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~W_i~ và ~V_i~ ~(1 \le V_i \le 10^9)~.
• Dòng tiếp theo chứa số nguyên ~Q~ (~1 \le Q \le 2.10^5~).
• ~Q~ dòng tiếp theo, dòng thứ ~j~ chứa ba số nguyên ~L_j~, ~R_j~ và ~Z_j~ ~(1 \le L_j \le R_j \le N)~.

Output

• Với mỗi kế hoạch, in ra trên một dòng là tổng giá trị lớn nhất các bảo vật có thể di dời.

Samples

4
3 2
1 3
2 6
4 1
3
1 3 3
2 4 7
1 4 7

9
10
11

5
1 10
2 12
3 13
4 14
5 15
7
1 5 9
1 5 10
1 5 11
1 5 12
1 5 13
1 5 14
1 5 15

39
49
50
51
52
54
64

Scoring

• Subtask ~1~ với ~21\%~ số điểm: ~N \le 20~; ~Q \le 10~; ~W_i, Z_j \le 10^9~
• Subtask ~2~ với ~29\%~ số điểm: ~Q \le 10~; ~W_i, Z_j \le 500~
• Subtask ~3~ với ~19\%~ số điểm: ~L_i = 1~ với mọi ~1 \le i \le N~; ~W_i, Z_j \le 500~
• Subtask ~4~ với ~31\%~ số điểm: ~W_i, Z_j \le 500~

Notes

Trong ví dụ đầu tiên, tổng giá trị lớn nhất các bảo vật được xác định như sau:

• Ở kế hoạch đầu tiên, nếu lựa chọn bảo vật thứ ~1~, tổng giá trị sẽ là ~2~, tuy nhiên nếu lựa chọn hai bảo vật thứ ~2~ và thứ ~3~, tổng giá trị sẽ là ~3+6=9~.
• Ở kế hoạch thứ hai, có thể lựa chọn cả ba bảo vật thứ ~2~, ~3~ và ~4~, tổng giá trị là ~3+6+1=10~.
• Ở kế hoạch thứ ba, ba bảo vật thứ ~1~, ~2~ và ~3~ được lựa chọn và tổng giá trị là ~2+3+6=11~.