Class Schedule

Time limit1sMemory limit128 MB

Summary

Choose one class per category to minimize class costs plus total travel from position 0 through the chosen rooms to position L.

Level: Medium6 of 10
Topics: Dynamic programming, Sorting
Solved: No attempts yet

Problem

At Fred Hacker's school there are $T \times C$ classes, divided into $C$ categories of $T$ classes each. The day begins with all the category-1 classes being taught at the same time; they all end together, then all the category-2 classes are taught, and so on. Fred must take exactly one class in each category. His goal is to choose the set of classes that minimizes the total energy needed to carry out his daily schedule.

The energy of a schedule is the sum of the energy required by the chosen classes themselves plus the energy spent moving from one class to the next through the day.

Specifically, taking the $j$ -th class of the $i$ -th category costs $E_{ij}$ units of energy. The rooms lie at integer positions (from $0$ to $L$ ) along a single hallway, and the $j$ -th class of the $i$ -th category is at position $P_{ij}$ . Fred starts the day at position $0$ , moves from class to class in category order according to his chosen schedule, and finally exits at position $L$ . Moving a distance $d$ costs $d$ units of energy.

Input

The first line contains $Z$ ( $Z \le 20$ ), the number of test cases, followed by the $Z$ test cases. Each test case begins with three space-separated integers $C$ , $T$ , and $L$ . Each of the next $C \times T$ lines gives the position and the energy cost of one class. The first $T$ lines are the classes of category 1, the next $T$ lines are the classes of category 2, and so on. No two classes in the same category share a position.

$1 \le C \le 25$
$1 \le T \le 1000$
$1 \le L \le 10^6$
$1 \le E_{ij} \le 10^6$
$0 \le P_{ij} \le L$

Output

For each test case, output a single line containing one integer: the minimum possible energy of a schedule that satisfies the constraints.

Hint

In this example, Fred must take 3 classes a day (one per category) and has 2 choices for each. The hallway has length 5.

One way to reach the minimum energy:

Go to the class at position 2. Total energy used so far: 3.
Next, go to the class at position 4. Total energy used so far: 6.
Then go to the class at position 3. Total energy used so far: 9.
Finally, leave the school at position 5. Total energy used: 11.

Examples2

Example 1
Input
```
1
3 2 5
2 1
3 1
4 1
1 3
1 4
3 2
```
Expected output
```
11
```
Example 2
Input
```
1
1 1 10
5 3
```
Expected output
```
13
```