Cho ~n~ đồ vật khác nhau, đồ vật thứ ~i~ có trọng lượng ~w_i~ và giá trị ~v_i~. Bạn cần trả lời ~q~ truy vấn, truy vấn thứ ~i~ cho bạn một chiếc túi có tải trọng tối đa là ~t_i~, và nhiệm vụ của bạn là chọn ra các đồ vật trong đoạn ~[l_i, r_i]~, mỗi đồ vật chỉ được lấy tối đa một lần trong truy vấn, sao cho tổng giá trị của các đồ vật lấy được là lớn nhất có thể mà tổng trọng lượng không vượt quá tải trọng chiếc túi.

Yêu cầu: Tính tổng tất cả các giá trị tìm được của cả ~q~ truy vấn.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (~n \le 10^4~).
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~w_i, v_i~ (~1 \le w_i \le 100, 1 \le v_i \le 10^4~).
• Dòng tiếp theo chứa số nguyên ~q~ (~q \le 10^5~).
• ~q~ dòng cuối cùng, dòng thứ ~i~ chứa 3 số nguyên ~l_i, r_i, t_i~ (~1 \le l_i \le r_i \le n, 1 \le t_i \le 100~).

Output

• Ghi ra một số nguyên duy nhất là tổng tất cả các giá trị tìm được của cả ~q~ truy vấn.

Sample Input 1

2
2 30
2 35
2
1 2 4
1 2 3

Sample Output 1

100