After the revolution, Aaeria has been unrated again and all his points have been taken away. Now, he is working his way back up. On DMOJ there are ~N~ problems, the ~i~th of which takes ~s_i~ minutes for him to implement and are worth ~v_i~ points.

Unfortunately, due to Aaeria's poor programming abilities, he must rely on Bruce for help. This year there are ~Q~ classes. During each class, he is taught the topics used in the problems from ~l~ to ~r~ and has ~t~ minutes to solve the problems. He can only solve the topics he has been taught that class because after the class, he looks at memes and forgets everything he learned.

Every time Aaeria solves problem ~i~, he gains ~v_i~ points. He can solve a problem at most once every class.

Help Aaeria regain his former glory and calculate how many points he can obtain by the end of the year.

Input

The first line contains ~N~.

The next ~N~ lines contain ~s_i~ and ~v_i~, representing time and value of the ~i~th problem.

The next line contains ~Q~.

The next ~Q~ lines contain ~l~, ~r~ and ~t~ indicating a class ~t~ minutes long covering problems from ~l~ to ~r~, including ~l~ and ~r~.

Output

The maximum total points that can be earned.

Constraints

For all subtasks:

~1 \le N,v_i \le 10^4~

~1 \le Q \le 10^5~

~1 \le s_i,t \le 100~

~1 \le l \le r \le N~

Subtask 1 [20%]

~r-l\le 100~

Subtask 2 [30%]

~Q\le 10^4~

Sample Input

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

Sample Output

100

Explanation

In the first class, he can solve problem 1 and 2. In the second class, he solves problem 2.

Sample Input

4
30 50
20 40
40 45
20 45
4
2 4 100
1 4 100
1 1 100
1 3 100

Sample Output

455

Sample Input

10
60 55
85 72
86 61
85 55
63 43
39 65
30 44
6 90
28 97
48 39
10
8 9 53
5 6 40
9 10 8
1 4 65
1 4 84
8 10 15
9 9 98
5 8 81
5 6 79
2 7 73

Sample Output

922