After the revolution, problems, the th of which takes minutes for him to implement and are worth points.

has been unrated again and all his points have been taken away. Now, he is working his way back up. On DMOJ there areUnfortunately, 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.

's poor programming abilities, he must rely on Bruce for help. This year Bruce is teachingEvery time , he gains points. He can solve a problem at most once every class.

solves problemHelp

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