D as in Daedalus

Daedalus is playing "Don't be greedy", a game for N players sitting around a table. Each player holds five cards labelled 1, 10, 100, 1000 and 10000 points. Once the game starts the players may not talk to each other, and the game runs for M rounds.

In each round the bank announces a budget B. Every player then picks one card and places it face down on the table. The bank turns the cards over, so all players see all N cards. If the sum of the points on the chosen cards is at most B, the bank pays each player exactly the points on the card that player chose. Otherwise nobody gets anything. Each player takes the card back before the next round. The players are very rational and want to maximize their points and minimize their regrets. What would you do in this situation, cooperate or defect?

Take the table below as an example. Daedalus won 10 points in total, because only the first round succeeded. Looking back on the game, he sees that 100 points in the first round and 10 points in the third round would have won him 110 points. That is 100 extra points, assuming the cards chosen by the other players stay the same.

Given the budget and the cards chosen in every round, compute the maximum total number of extra points Daedalus could have won by picking the best possible card in each round, assuming the cards chosen by the other players stay the same.

The first line contains two integers N and M, the number of players and the number of rounds ($1 \le N \le 20$, $1 \le M \le 50$).

Each of the next M lines describes one round. The line starts with an integer B, the budget ($1 \le B \le 10^6$), followed by N integers $C_1, C_2, \dots, C_N$, where $C_i$ is the card the i-th player chose in that round and $C_i \in \{1, 10, 100, 1000, 10000\}$. Daedalus is the first player.

Print one line with the maximum total number of extra points Daedalus could have won by picking the best possible card in each round, assuming the cards chosen by the other players stay the same.