Clash Royale (Small)

Time limit5sMemory limit512 MB

Summary

Spend up to M coins upgrading N cards, then pick 8 cards to maximize the deck's total attack power.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Sorting
Solved: No attempts yet

Problem

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 fighting, Shawn has collected a total of $M$ coins and has decided to upgrade some of his cards. Shawn has $N$ cards. The $i$ -th card can be at 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 raising 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. Help him do this. 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.

Input

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

Each test case starts with a line containing $M$ and $N$ , the number of coins and the number of cards Shawn has. Then $N$ blocks follow, and the $i$ -th block consists of 3 lines describing the $i$ -th card.

The first line contains $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}$ , the number of coins needed to upgrade the card when it is at level $1, 2, \ldots, K_i-1$ . If $K_i = 1$ , this line is empty.

Output

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

Constraints

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

Hint

In the first sample test case, you can 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.

In the second sample test case, Shawn has 10 cards, so he picks 8 of them for the deck.

Examples1

Example 1

Input

2
20 8
3 1
1 10 100
1 2
3 1
1 10 100
1 3
3 1
1 10 100
1 4
3 1
1 10 100
1 5
3 1
1 10 100
1 6
3 1
1 10 100
1 7
3 1
1 10 100
1 8
3 1
1 10 100
1 9
30 10
4 1
1 10 100 200
1 2 3
3 1
1 10 100
2 4
3 1
1 10 100
3 6
4 2
1 10 100 200
4 8 16
3 1
1 10 100
5 10
3 1
1 10 100
6 12
3 1
1 10 100
7 14
3 1
1 10 100
8 16
3 1
1 10 100
9 18
3 1
1 10 100
10 20

Expected output

Case #1: 422
Case #2: 504