After the revolution, problems, the of which takes minutes for him to implement and are worth points. Each problem also has a topic. The 1st problem has topic 1, the 2nd problem has topic 2, and so on.

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 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 there areEvery 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