VPEX P5 - Points Redistribution

View as PDF

Submit solution

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

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

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

Comments

There are no comments at the moment.