VPEX P5 - Points Redistribution

View as PDF

Submit solution


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

Problem types

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 ith of which takes si minutes for him to implement and are worth vi 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 vi 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.

Input Specification

The first line contains N.

The next N lines contain si and vi, 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 Specification

The maximum total points that can be earned.

Constraints

For all subtasks:

1N,vi104

1Q105

1si,t100

1lrN

Subtask 1 [20%]

rl100

Subtask 2 [30%]

Q104

Subtask 3 [50%]

No additional constraints.

Sample Input 1

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

Sample Output 1

Copy
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

Copy
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

Copy
455

Sample Input 3

Copy
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

Copy
922

Comments

There are no comments at the moment.