멀린 QA (라지)

에디스는 주문 공장 멀린 사의 품질 보증 부서에서 일하는 젊은 마법사다. 멀린이 새로 고안한 주문을 검사하는 일을 맡고 있다. 주문마다 필요한 재료의 종류와 양이 정확히 정해져 있고, 그 재료를 다른 재료로 정해진 양만큼 바꾼다. 에디스는 각 주문이 제대로 동작하는지 확인하려고 주문을 하나씩 모두 시전해야 한다.

주문을 시전하려면 필요한 재료를 필요한 양만큼 갖고 있어야 한다. 앞선 주문으로 이미 만들어 둔 재료가 있으면 그것부터 반드시 쓴다. 그러고도 모자란 양은 멀린의 창고에서 가져오며, 창고에서 가져오는 재료에는 값을 치르지 않는다. 처음에는 재료가 하나도 없고, 마지막까지 쓰지 않고 남은 재료는 모두 에디스가 가진다.

에디스는 수습 기간에 최대한 많이 벌고 싶다. 주어진 주문 $N$개를 각각 정확히 한 번씩 시전해야 하지만 순서는 마음대로 정할 수 있다. 모든 주문이 설명대로 동작한다고 할 때, 마지막에 남는 재료의 가치를 가장 크게 만드는 순서를 찾아 그 가치를 구하라.

재료의 양은 모두 달러로 나타낸다. 예를 들어 검사 목록에 금, 황, 두꺼비를 다루는 주문 3개가 있다고 하자.

1. 금 7달러어치를 쓰고 황 5달러어치를 만든다.
2. 아무것도 쓰지 않고 금 10달러어치와 황 10달러어치를 만든다.
3. 황 20달러어치를 쓰고 금 3달러어치와 두꺼비 2달러어치를 만든다.

1, 2, 3 순서로 시전하면 먼저 첫 번째 주문에 쓸 금 7달러어치를 창고에서 가져와 황 5달러어치를 얻는다. 두 번째 주문까지 마치면 금 10달러어치와 황 15달러어치가 남는다. 세 번째 주문은 황 20달러어치가 필요하므로 갖고 있던 황 15달러어치를 모두 쓰고 모자란 5달러어치를 창고에서 가져온다. 끝나고 나면 금 13달러어치와 두꺼비 2달러어치, 합쳐서 15달러가 남는다.

3, 1, 2 순서가 더 낫다. 세 번째 주문을 아무 재료도 없을 때 시전하므로 필요한 황을 전부 창고에서 가져오고, 나중에 만든 황은 한 푼도 쓰지 않는다. 끝나고 나면 금 10달러어치, 황 15달러어치, 두꺼비 2달러어치가 남아 모두 27달러가 된다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 $N$과 $M$이 주어진다. $M$은 세상에 존재하는 재료의 가짓수다. 이어지는 $N$개 줄에는 주문 하나를 나타내는 정수 $M$개가 주어진다. $j$번째 정수는 그 주문에서 $j$번째 재료가 갖는 값이다. 음수는 주문이 쓰는 재료의 달러 비용, 양수는 주문이 만드는 재료의 달러 가치, 0은 그 주문이 쓰지도 만들지도 않는 재료를 뜻한다. 한 주문이 같은 재료를 쓰면서 동시에 만드는 일은 없다.

제한

• $1 \le T \le 100$
• $1 \le N \le 100$
• $1 \le M \le 8$
• 주문에 주어지는 각 정수는 $-100$ 이상 $100$ 이하다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 주문 $N$개를 모두 시전한 뒤 에디스가 가질 수 있는 재료 가치의 최댓값이다.