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
Unfortunately, due to [redacted]'s poor programming abilities, he must rely on Bruce for help. This year there are
Every time [redacted] solves problem
Help [redacted] regain his ranking and calculate how many points can be obtained by the end of the year.
Input Specification
The first line contains
The next
The next line contains
The next
Output Specification
The maximum total points that can be earned.
Constraints
For all subtasks:
Subtask 1 [20%]
Subtask 2 [30%]
Subtask 3 [50%]
No additional constraints.
Sample Input 1
2
2 30
2 35
2
1 2 4
1 2 3
Sample Output 1
100
Explanation for Sample Output 1
In the first class, he can solve problems 1 and 2. In the second class, he solves problem 2.
Sample Input 2
4
30 50
20 40
40 45
20 45
4
2 4 100
1 4 100
1 1 100
1 3 100
Sample Output 2
455
Sample Input 3
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 3
922
Comments