클래시 로얄 (Large)

클래시 로얄은 실시간 전략 카드 게임이다. 각 카드에는 공격력과 레벨이 있다. 플레이어는 카드 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}$가 주어진다.
• 셋째 줄에는 정수 $K_i - 1$개 $C_{i,1}, C_{i,2}, \ldots, C_{i,K_i-1}$이 주어진다. $C_{i,j}$는 현재 레벨이 $j$인 카드를 한 레벨 올리는 데 필요한 코인의 수이다. $K_i = 1$이면 이 줄은 비어 있다.

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

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

첫 번째 예제에서는 앞의 카드 4장을 레벨 3으로, 5번째와 6번째 카드를 레벨 2로 업그레이드하고 마지막 카드 2장은 레벨 1로 둔다. 이때 드는 코인은 $(1+2)+(1+3)+(1+4)+(1+5)+1+1=20$개이고, 덱의 총 공격력은 $100+100+100+100+10+10+1+1=422$이다. 이 값이 만들 수 있는 최댓값이다.