1 人解决，2 人已尝试。
1 份提交通过，共有 143 份提交。
9.9 EMB 奖励。
单点时限: 1.0 sec
内存限制: 256 MB
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; the total attack power of a deck is the sum of the attack power of each of its cards. Players fight with each other by placing cards from their battle decks into the battle arena. The winner of a battle is rewarded with coins, which can be used to upgrade cards. Upgrading a card increases its attack power.
After days of arena fighting, Little Shawn has accumulated a total of $M$ coins. He has decided to upgrade some of his cards. Little Shawn has $N$ cards. The $i$-th card can have any level from $1$ through $K_i$; the attack power for the $j$-th level is $A_{i,j}$. Cards must be upgraded one level at a time; the price to upgrade the $i$-th card from level $j$ to level $j+1$ costs $C_{i,j}$ coins. The $i$-th card is currently at level $L_i$ before Little Shawn has upgraded any cards.
Little Shawn wants to use some or all of his coins to upgrade cards, and then form a deck of exactly 8 cards, so that the deck’s total attack power is as large as possible. Can you 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.
The test case starts with 2 integers $M$ $(1 \leq M \leq 10^9)$ and $N$ $(8 \leq N \leq 12)$, the number of coins and the number of cards that Little Shawn possesses. Then $N$ blocks follow. The $i$-th block consists of 3 lines describing the $i$-th card. The first line contains two integers $K_i$ and $L_i$ $(1 \leq L_i \leq K_i \leq 10)$, the maximum possible level and current level of the card. The second line contains $K_i$ integers $A_{i,1}, A_{i,2}, \ldots, A_{i,K_i}$ $(1 \leq A_{i,j} \leq 10^9, A_{i,j} < A_{i,j+1})$, the attack power of each level. The third line contains $K_{i-1}$ integers $C_{i,1}, C_{i,2}, \ldots, C_{i,K_{i-1}}$ $(1 \leq C_{i,j} \leq 10^9)$, the number of coins required to upgrade a card that is currently at level $1, 2, \ldots, K_{i-1}$.
Output an answer, that is the maximal possible total attack power of a deck that Little Shawn can form, using the coins that he has.
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
422
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
504
In sample case #1, you can upgrade the first 4 cards to level 3, upgrade the 5th and 6th card to level 2, keep the last 2 cards level 1. This will cost you (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 maximal possible we can get.
Sample case #2 would only appear in Large dataset.
1 人解决，2 人已尝试。
1 份提交通过，共有 143 份提交。
9.9 EMB 奖励。