Points Redistribution
Description
After the revolution, [redacted] 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^\text{th}$ of which takes $s_i$ minutes for him to implement and are worth $v_i$ points.
Unfortunately, due to [redacted]'s poor programming abilities, he must rely on Bruce for help. This year there are $Q$ classes. During each class, he is taught 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 [redacted] solves problem $i$, they gain $v_i$ points. **Each problem can be solved at most once per class.**
Help [redacted] regain his ranking and calculate how many points can be obtained by the end of the year.
The first line contains $N$.
The next $N$ lines contain $s_i$ and $v_i$, representing time and value of the $i^\text{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$.
## 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$
### Subtask 3 [50 No additional constraints.
The maximum total points that can be earned.
Input
The first line contains $N$.
The next $N$ lines contain $s_i$ and $v_i$, representing time and value of the $i^\text{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$.
## 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$
### Subtask 3 [50 No additional constraints.
Output
The maximum total points that can be earned.
2
2 30
2 35
2
1 2 4
1 2 3
4
30 50
20 40
40 45
20 45
4
2 4 100
1 4 100
1 1 100
1 3 100
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
100
455
922
Note
Sample 1: In the first class, he can solve problems 1 and 2. In the second class, he solves problem 2.