클래시 로얄 (Small)

클래시 로얄은 실시간 전략 카드 게임이다. 카드마다 공격력과 레벨이 있다. 플레이어는 카드 8장을 골라 배틀 덱을 만들며, 덱의 총 공격력은 덱에 든 카드 공격력의 합이다. 플레이어는 배틀 덱의 카드를 경기장에 내려놓으며 서로 싸운다. 배틀에서 이기면 코인을 받고, 코인으로 카드를 업그레이드할 수 있다. 카드를 업그레이드하면 공격력이 오른다.

며칠 동안 경기장에서 싸운 끝에 숀은 코인을 모두 $M$개 모았고, 카드 몇 장을 업그레이드하기로 했다. 숀에게는 카드가 $N$장 있다. $i$번째 카드의 레벨은 $1$부터 $K_i$까지이며, 레벨이 $j$일 때 공격력은 $A_{i,j}$이다. 카드는 한 번에 한 레벨씩만 올릴 수 있고, $i$번째 카드를 레벨 $j$에서 레벨 $j+1$로 올리려면 코인 $C_{i,j}$개가 든다. 업그레이드를 하기 전 $i$번째 카드의 레벨은 $L_i$이다.

숀은 코인의 일부 또는 전부를 써서 카드를 업그레이드한 뒤, 정확히 8장으로 덱을 만들려고 한다. 덱의 총 공격력이 가장 커지도록 도와주자. 코인이 충분하면 같은 카드를 여러 번 업그레이드해도 되고, 모든 카드를 업그레이드할 필요는 없다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 숀이 가진 코인의 수 $M$과 카드의 수 $N$이 주어진다. 그다음 $N$개의 블록이 이어지며, $i$번째 블록은 $i$번째 카드를 설명하는 세 줄로 이루어진다.

• 첫째 줄에는 카드의 최대 레벨 $K_i$와 현재 레벨 $L_i$가 주어진다.
• 둘째 줄에는 각 레벨의 공격력 $A_{i,1}, A_{i,2}, \ldots, A_{i,K_i}$가 주어진다.
• 셋째 줄에는 레벨이 $1, 2, \ldots, K_i-1$인 카드를 한 레벨 올리는 데 드는 코인의 수 $C_{i,1}, C_{i,2}, \ldots, C_{i,K_i-1}$이 주어진다. $K_i = 1$이면 이 줄은 빈 줄이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 숀이 가진 코인으로 만들 수 있는 덱의 총 공격력 중 최댓값이다.

• $1 \le T \le 100$
• $1 \le M \le 1000$
• $8 \le N \le 100$
• $1 \le K_i \le 10$
• $1 \le L_i \le K_i$
• $1 \le A_{i,j} \le 1000$
• $A_{i,j} < A_{i,j+1}$
• $1 \le C_{i,j} \le 1000$

예제의 첫 번째 테스트 케이스에서는 앞의 카드 4장을 레벨 3으로, 5번째와 6번째 카드를 레벨 2로 올리고 마지막 두 장은 레벨 1로 둔다. 비용은 $(1+2)+(1+3)+(1+4)+(1+5)+1+1=20$코인이고, 총 공격력은 $100+100+100+100+10+10+1+1=422$로 가능한 최댓값이다.

두 번째 테스트 케이스에서는 카드가 10장이므로 그중 8장을 골라 덱을 만든다.