Class Schedule#2645
At Fred Hacker's school, there are C \times T classes, divided into categories with classes each. The day begins with all classes from category being taught simultaneously. These finish at the same time, then all classes from category are taught, and so on. Fred must take exactly one class from each category. His goal is to choose a set of classes that minimizes the total amount of "energy" required to follow his daily schedule.
The energy of a schedule is the sum of the energies required for the chosen classes and the energy used to move from one class to the next according to the schedule.
Taking the th class in the th category requires e_{ij} units of energy. Classrooms are located at integer positions along a hallway (numbered from to ). The th class in the th category is at position p_{ij}. Fred starts at position , visits the chosen classrooms in order, and ends at position . Moving a distance costs units of energy.
The first line contains (z \leq 20), the number of test cases. Each test case starts with three integers , , and (1 \leq c \leq 25, 1 \leq t \leq 1000, 1 \leq l \leq 1\,000\,000). The next c \times t lines each describe a class with its location and energy cost. The first lines are for category , the next lines for category , and so on. No two classes in the same category have the same location. It is guaranteed that 1 \leq e_{ij} \leq 1\,000\,000 and 0 \leq p_{ij} \leq l.
Explanation of Sample Input
Fred must take classes per day, and has choices each day. The hallway is units long. Fred's first possible class is in room and requires unit of energy daily, and so on.
For each test case, print a single integer in a separate line — the minimal possible energy of a schedule meeting the constraints.
Example 1