다이달로스의 후회

문제

다이달로스는 "욕심부리지 않기" 게임을 하고 있다. N명이 탁자에 둘러앉고, 각자 1점, 10점, 100점, 1000점, 10000점이 적힌 카드를 한 장씩, 모두 다섯 장 가진다. 게임이 시작되면 참가자끼리 말을 나눌 수 없으며, 라운드는 M번 진행된다.

각 라운드에서 은행이 예산 B를 발표한다. 그러면 각 참가자는 카드 한 장을 골라 뒷면이 보이게 탁자에 내려놓는다. 은행이 카드를 모두 뒤집으면 참가자는 N장의 카드를 전부 볼 수 있다. 낸 카드의 점수 합이 B 이하이면 은행은 각 참가자에게 자신이 낸 카드의 점수를 그대로 준다. 합이 B를 넘으면 아무도 점수를 받지 못한다. 다음 라운드가 시작되기 전에 각자 낸 카드를 돌려받는다. 참가자는 모두 매우 합리적이어서 점수는 최대로, 후회는 최소로 남기고 싶어 한다. 이런 상황에서 당신이라면 협력하겠는가, 배신하겠는가?

아래 표를 예로 보자. 첫 번째 라운드만 성공했으므로 다이달로스가 실제로 얻은 점수는 10점이다. 그런데 게임이 끝나고 돌아보니, 첫 번째 라운드에 100점 카드를, 세 번째 라운드에 10점 카드를 냈다면 110점을 얻을 수 있었다. 다른 참가자가 낸 카드가 그대로라고 가정하면 100점을 더 얻을 수 있었던 셈이다.

라운드	예산 B	다이달로스	이아픽스	이카로스	아리아드네	미노스	합	결과
1	300	10	100	10	1	10	131	성공
2	1100	100	10	100	1	1000	1211	실패
3	1200	100	100	10	1	1000	1211	실패

각 라운드의 예산과 참가자가 낸 카드가 주어진다. 다른 참가자가 낸 카드가 그대로라고 가정할 때, 다이달로스가 매 라운드마다 가장 좋은 카드를 냈다면 실제보다 몇 점을 더 얻을 수 있었는지 구하라.

입력

첫째 줄에 참가자 수 N과 라운드 수 M이 주어진다 ( $1 \le N \le 20$ , $1 \le M \le 50$ ).

다음 M개의 줄에는 라운드가 한 줄에 하나씩 주어진다. 각 줄은 예산 B로 시작하고 ( $1 \le B \le 10^6$ ), 이어서 N개의 정수 $C_1, C_2, \dots, C_N$ 이 주어진다. $C_i$ 는 그 라운드에서 i번째 참가자가 낸 카드의 점수이며, $C_i \in \{1, 10, 100, 1000, 10000\}$ 이다. 다이달로스는 첫 번째 참가자이다.

출력

다른 참가자가 낸 카드가 그대로라고 가정할 때, 다이달로스가 매 라운드마다 가장 좋은 카드를 냈다면 추가로 얻을 수 있었던 점수의 최댓값을 한 줄에 출력한다.