고정 지능 분할 대회 운영

한 팀의 전체 지적 능력은 여러 명의 팀원에게 나누어져 있습니다. 각 팀원은 고정된 양의 ‘지능(밝기)’을 가지며, 팀원마다 그 값이 다를 수 있습니다. 모든 팀원의 지능을 합하면 팀 전체의 지적 능력이 됩니다.

여러 개의 문제가 주어지면, 팀은 각 문제를 팀원에게 배정하여 동시에 풀 수 있도록 해야 합니다. 이때 한 팀원은 같은 시각에 두 문제를 동시에 풀 수 없으며, 문제는 자신의 최소 지능 요구치 이상인 팀원에게만 배정할 수 있습니다. 각 문제를 푸는 데 걸리는 시간은 그 문제를 맡은 팀원의 지능에 따라 달라집니다. 즉, 지능이 더 높은 팀원에게 맡기면 풀이 시간이 짧아질 수도, 오히려 길어질 수도 있습니다.

모든 문제는 대회 시작 시각인 시각 $0$에 동시에 제출됩니다. 한 문제의 풀이 시간(solution time)은 그 문제가 해결된 시각을 뜻합니다(제출 시각이 $0$이므로 해결된 시각과 같습니다).

각 문제를 어떤 팀원에게 배정하고 각 팀원이 맡은 문제들을 어떤 순서로 풀지를 정하여(한 팀원이 두 문제를 동시에 풀지 않도록), 모든 문제의 풀이 시간의 합을 최소로 만드는 것이 목표입니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스의 첫 줄에는 두 정수 $m$과 $n$이 주어집니다. $m$은 팀원의 수($1 \le m \le 3$)이고, $n$은 풀어야 할 문제의 수($1 \le n \le 10$)입니다.

다음 줄에는 $m$개의 양의 정수가 주어지며, 각 팀원의 지능을 순서대로 나타냅니다.

이어지는 $n$개의 줄은 각 문제의 ‘시간-지능 관계’를 나타냅니다. 각 줄은 양의 정수 $k$($k \le 10$)로 시작하고, 그 뒤에 $k$개의 양의 정수 쌍 $s_1\ t_1\ s_2\ t_2\ \dots\ s_k\ t_k$가 주어집니다. 이 값들은 $1 \le i < k$에 대해 $s_i < s_{i+1}$을 만족합니다. 문제의 최소 지능 요구치는 $s_1$이며, 지능이 이보다 작은 팀원은 그 문제를 풀 수 없습니다. 지능이 $s$인 팀원이 이 문제를 풀 때, 어떤 $i$에 대해 $s_i \le s < s_{i+1}$이면 풀이 시간은 $t_i$입니다. 지능이 $s_k$ 이상이면 풀이 시간은 $t_k$입니다.

마지막 테스트 케이스 다음에는 두 정수 $0\ 0$이 담긴 줄이 오며, 이는 입력의 끝을 나타냅니다.

각 문제는 다른 팀원이 같은 시각에 몇 개의 문제를 풀고 있든 상관없이, 해당 지능에 대해 정해진 시간만큼 정확히 걸려서 해결된다고 가정합니다. 어떤 문제의 지능 요구치도 가장 지능이 높은 팀원의 지능을 넘지 않습니다.

각 테스트 케이스마다 한 줄에 Case X: T 형식으로 출력합니다. 여기서 $X$는 테스트 케이스 번호($1$부터 시작하여 차례로 $1$씩 증가)이고, $T$는 모든 문제의 풀이 시간 합의 최솟값입니다. 즉, 유효한 모든 배정과 풀이 순서를 통틀어 $n$개 문제의 풀이 시간을 모두 더한 값 중 가장 작은 값을 정수로 출력합니다.