Fixed Partition Contest Management

A team's total intellectual capacity is split among several members. Each member has a fixed amount of intelligence (its “brightness”), and different members may have different amounts; the sum of all members' brightness is the team's total intellectual capacity.

You are given a set of problems, and the team must assign each problem to a member so that they can be solved concurrently. No member may work on two problems at the same time, and a problem may only be given to a member whose brightness is at least the problem's minimum requirement. The time needed to solve a problem depends on the brightness of the member who solves it: giving it to a brighter member may make the solution time shorter, or longer.

Every problem is submitted at the start of the contest, time $0$. The solution time of a problem is the moment at which it is solved (equal to its completion time, since it is submitted at time $0$).

Choose which member solves each problem, and the order in which each member solves its assigned problems (so that no member solves two problems at once), to minimize the sum of the solution times of all problems.

The input contains several test cases. Each test case begins with a line containing two integers $m$ and $n$, where $m$ is the number of team members ($1 \le m \le 3$) and $n$ is the number of problems to solve ($1 \le n \le 10$).

The next line contains $m$ positive integers giving the brightness of each member, in order.

The following $n$ lines describe the time–brightness tradeoff of each problem. Each line starts with a positive integer $k$ ($k \le 10$), followed by $k$ pairs of positive integers $s_1\ t_1\ s_2\ t_2\ \dots\ s_k\ t_k$ satisfying $s_i < s_{i+1}$ for $1 \le i < k$. The problem's minimum brightness requirement is $s_1$; a member with less brightness cannot solve it. If a member with brightness $s$ solves the problem and $s_i \le s < s_{i+1}$ for some $i$, the solution time is $t_i$; if the member's brightness is at least $s_k$, the solution time is $t_k$.

The line $0\ 0$ follows the last test case and marks the end of the input.

Each problem takes exactly the time specified for the given brightness, no matter how many other problems other members are solving at the same time. No problem has a brightness requirement larger than the brightest member's brightness.

For each test case, print one line in the form Case X: T, where $X$ is the test case number (starting at $1$ and increasing by $1$) and $T$ is the minimum achievable sum of the solution times of all problems — that is, over all valid assignments and orderings, the smallest possible total of the $n$ problems' solution times, printed as an integer.