Tzovex is currently taking a course in real analysis. Unfortunately for him and his class, they are having trouble following the lectures and are now struggling with a particular homework assignment that is due in days. The homework assignment consists of questions, the th of which has a value of . Including himself, Tzovex's class consists of students, the th of which having solved the first problems while being unable to solve the rest. However, the professor is willing to help out students in extra classes, each of which is dedicated to a single problem. In particular, help will be available for the th problem between and (inclusive) days from today. The th student only has time for one extra class, and he can only attend it if it happens in exactly days. The professor also has a unique way of grading assignments. Rather than giving the students marks, he instead gives them penalties. Going from the first to the last problem, the th problem that a student did not solve will earn them times the value of the problem in penalties. Assuming that no student will solve any extra problems on their own, determine the minimum possible penalty that each of the students can achieve.

#### Input Specification

The first line contains three space-separated integers, , , and .

lines follow, the th of which contains three space separated integers, , , and .

more lines follow, the th of which contains two space separated integers, and .

#### Output Specification

Output lines, the th of which containing a single integer, the minimum possible penalty that the th student can achieve.

#### Constraints

In all subtasks,

##### Subtask 1 [5%]

##### Subtask 2 [10%]

##### Subtask 3 [35%]

and

##### Subtask 4 [50%]

No additional constraints.

#### Sample Input

```
5 4 5
5 3 5
2 1 3
3 2 4
7 4 5
0 4
1 3
2 5
3 2
4 1
```

#### Sample Output

```
18
16
3
7
0
```

#### Explanation for Sample Output

The optimal move for student is to attend the lecture for problem resulting in a penalty of .

The optimal move for student is to attend the lecture for problem resulting in a penalty of .

The optimal move for student is to attend the lecture for problem resulting in a penalty of .

Student can't attend any useful lectures and so has a penalty of .

Student doesn't need any lectures and has a penalty of .

## Comments