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

has been unrated again and all their points have been taken away. Now, they are working their way back up. On DMOJ there areUnfortunately, due to classes. During each class, Aaeria is taught the topics used in the problems from to and has minutes to solve the problems. Aaeria can only solve the topics taught in that class because after the class, Aaeria looks at memes and forgets everything they learned.

's poor programming abilities, they must rely on Bruce for help. This year, Bruce is teachingEvery time , they gains points. **Each problem can be solved at most once per class.**

Help

regain their former status and calculate how many points can be obtained 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%]

#### Subtask 3 [50%]

No additional constraints.

#### Sample Input 1

```
2
2 30
2 35
2
1 2 4
1 2 3
```

#### Sample Output 1

`100`

#### Explanation for Sample Output 1

In the first class, he can solve problem 1 and 2. In the second class, he solves problem 2.

#### Sample Input 2

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

`455`

#### Sample Input 3

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

`922`

## Comments