Clash Royale (Large)

Clash Royale is a real-time strategy card game. Each card has an attack power and a level. Each player picks 8 cards to form a battle deck, and the total attack power of a deck is the sum of the attack powers of its cards. Players fight each other by placing cards from their battle decks into the arena. The winner of a battle receives coins, which can be used to upgrade cards. Upgrading a card increases its attack power.

After days of arena fights, Little Shawn has collected $M$ coins in total, and he has decided to upgrade some of his cards. Shawn has $N$ cards. The $i$-th card can have any level from 1 through $K_i$, and its attack power at level $j$ is $A_{i,j}$. A card is upgraded one level at a time, and upgrading the $i$-th card from level $j$ to level $j+1$ costs $C_{i,j}$ coins. Before any upgrade, the $i$-th card is at level $L_i$.

Shawn wants to spend some or all of his coins on upgrades and then form a deck of exactly 8 cards whose total attack power is as large as possible. He can upgrade the same card more than once as long as he can afford it, and he does not have to upgrade every card. Find the maximum total attack power of a deck Shawn can form.

The first line contains the number of test cases $T$. $T$ test cases follow.

Each test case starts with a line containing two integers $M$ and $N$: the number of coins and the number of cards Shawn has. Then $N$ blocks follow. The $i$-th block has three lines that describe the $i$-th card.

• The first line contains two integers $K_i$ and $L_i$: the maximum level and the current level of the card.
• The second line contains $K_i$ integers $A_{i,1}, A_{i,2}, \ldots, A_{i,K_i}$: the attack power at each level.
• The third line contains $K_i - 1$ integers $C_{i,1}, C_{i,2}, \ldots, C_{i,K_i-1}$, where $C_{i,j}$ is the number of coins needed to upgrade the card when it is at level $j$. If $K_i = 1$, this line is empty.

For each test case, print one line in the form Case #x: y, where x is the test case number (starting from 1) and y is the maximum total attack power of a deck Shawn can form with the coins he has.

• $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$

In the first sample case, upgrade the first 4 cards to level 3, upgrade the 5th and 6th cards to level 2, and keep the last 2 cards at level 1. This costs $(1+2)+(1+3)+(1+4)+(1+5)+1+1=20$ coins, and the total attack power is $100+100+100+100+10+10+1+1=422$, which is the maximum possible.