클래시 로얄

클래시 로얄은 실시간 전략 카드 게임이다. 각 카드에는 공격력과 레벨이 있다. 각 플레이어는 8장의 카드를 골라 전투 덱을 구성한다. 덱의 총공격력은 덱에 포함된 각 카드의 공격력의 합이다. 플레이어들은 자신의 전투 덱에서 카드를 전투 경기장에 내놓으며 서로 싸운다. 전투의 승자는 코인을 보상으로 받으며, 이 코인은 카드를 강화하는 데 사용할 수 있다. 카드를 강화하면 공격력이 증가한다.

며칠 동안 경기장에서 싸운 끝에, Little Shawn은 총 M개의 코인을 모았다. 그는 자신의 카드 중 일부를 강화하기로 했다. Little Shawn에게는 N장의 카드가 있다. i번째 카드는 1부터 $K_{i}$까지의 어떤 레벨도 될 수 있으며, j번째 레벨의 공격력은 $A_{i,j}$이다. 카드는 한 번에 한 레벨씩 강화해야 한다. i번째 카드를 레벨 j에서 레벨 j+1로 강화하는 데 드는 비용은 $C_{i,j}$코인이다. Little Shawn이 어떤 카드도 강화하기 전에 i번째 카드의 현재 레벨은 $L_{i}$이다.

Little Shawn은 코인의 일부 또는 전부를 사용해 카드를 강화한 다음, 정확히 8장의 카드로 덱을 구성하여 덱의 총공격력을 최대한 크게 만들고자 한다. 그가 이렇게 할 수 있도록 도와줄 수 있는가? 비용을 감당할 수 있는 한 같은 카드를 두 번 이상 강화할 수 있으며, 모든 카드를 강화할 필요는 없다.

제한

시간 제한: 테스트 세트당 60초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 1 ≤ $K_{i}$ ≤ 10. 1 ≤ $L_{i}$ ≤ $K_{i}$. $A_{i,j}$ < $A_{i,j+1}$.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ M ≤ 1,000. N = 8. 1 ≤ $A_{i,j}$ ≤ 1,000. 1 ≤ $C_{i,j}$ ≤ 1,000.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ M ≤ 1,000,000,000. 8 ≤ N ≤ 12. 1 ≤ $A_{i,j}$ ≤ 1,000,000,000. 1 ≤ $C_{i,j}$ ≤ 1,000,000,000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 Little Shawn이 가진 코인의 수와 카드의 수를 나타내는 2개의 정수 M과 N으로 시작한다. 그다음 N개의 블록이 주어진다. i번째 블록은 i번째 카드를 설명하는 3개의 줄로 이루어진다. 첫 줄에는 카드가 가질 수 있는 최대 레벨과 현재 레벨을 나타내는 두 정수 $K_{i}$와 $L_{i}$가 주어진다. 둘째 줄에는 각 레벨의 공격력을 나타내는 $K_{i}$개의 정수 $A_{i,1}$, $A_{i,2}$, ..., A_{i,$K_{i}$}가 주어진다. 셋째 줄에는 현재 레벨이 각각 1, 2, ..., $K_{i}$-1인 카드를 강화하는 데 필요한 코인의 수를 나타내는 $K_{i}$-1개의 정수 $C_{i,1}$, $C_{i,2}$, ..., C_{i,$K_{i}$-1}가 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며, 1부터 시작한다. y는 Little Shawn이 가진 코인을 사용하여 구성할 수 있는 덱의 가능한 최대 총공격력이다.

예제 케이스 #1에서는 처음 4장의 카드를 레벨 3로 강화하고, 5th 카드와 6th 카드를 레벨 2으로 강화하며, 마지막 2장의 카드는 레벨 1로 유지할 수 있다. 여기에는 (1+2)+(1+3)+(1+4)+(1+5)+1+1=20개의 코인이 들고, 총공격력은 100+100+100+100+10+10+1+1=422로, 이는 얻을 수 있는 가능한 최댓값이다.

예제 케이스 #2는 큰 데이터 세트에만 나타난다.