After the revolution, problems, the
th of which takes
minutes for him to implement and are worth
points.
Unfortunately, due to classes. During each class, he is taught the topics used in the problems from
to
and has
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 , he gains
points. He can solve a problem at most once every class.
Help
regain his former glory and calculate how many points he can obtain by the end of the year.Input
The first line contains .
The next lines contain
and
, representing time and value of the
th problem.
The next line contains .
The next lines contain
,
and
indicating a class
minutes long covering problems from
to
, including
and
.
Output
The maximum total points that can be earned.
Constraints
For all subtasks:
Subtask 1 [20%]
Subtask 2 [30%]
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