VPEX P5 - Points Redistribution

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 0.8s
Memory limit: 128M

Author:
Problem types

After the revolution, Aaeria has been unrated again and all their points have been taken away. Now, they are working their way back up. On DMOJ there are N problems, the ith of which takes s_i minutes to implement and are worth v_i points.

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

Every time Aaeria solves problem i, they gains v_i points. Each problem can be solved at most once per class.

Help Aaeria regain their former status and calculate how many points can be obtained 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 ith 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

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 problem 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

There are no comments at the moment.