멀린 사의 주문 검사

Edythe는 마법 주문 공장 Merlin, Inc.의 품질 관리 부서에서 일하는 젊은 마법사다. Merlin이 직접 고안한 주문을 검사하는 것이 그의 일이다. 주문 하나는 정해진 양의 재료를 소모해서 다른 재료를 정해진 양만큼 만들어 낸다. Edythe는 주문이 제대로 작동하는지 확인하려고 각 주문을 정확히 한 번씩 시전한다.

필요한 재료를 모두 갖춘 상태에서만 주문을 시전할 수 있다. 앞선 주문으로 만들어 둔 재료가 있으면 그것을 먼저 써야 한다. 그러고도 모자라면 모자란 만큼만 Merlin의 창고에서 가져온다. 창고에서 가져오는 재료에는 값을 치르지 않는다. 처음에는 재료를 하나도 가지고 있지 않고, 마지막에 쓰고 남은 재료는 모두 Edythe의 몫이다.

Edythe는 마지막에 남는 재료의 가치를 최대로 만들고 싶다. 주어진 $N$개의 주문을 각각 정확히 한 번씩 시전해야 하지만 순서는 마음대로 정할 수 있다. 모든 주문이 설명대로 작동한다고 할 때, 마지막에 남는 재료 가치의 최댓값을 구하라.

예를 들어 검사 목록에 다음 세 주문이 있다고 하자.

1. 금 $7어치를 넣으면 황 $5어치가 나온다.
2. 아무것도 넣지 않아도 금 $10어치와 황 $10어치가 나온다.
3. 황 $20어치를 넣으면 금 $3어치와 두꺼비 $2어치가 나온다.

첫 주문은 금을 황으로 바꾸고, 둘째 주문은 아무것도 없는 데서 금과 황을 만들어 내며, 셋째 주문은 황을 금과 두꺼비로 바꾼다.

1, 2, 3 순서로 시전한다고 하자. 첫 주문에 쓸 금 $7어치를 창고에서 가져와야 한다. 첫 주문과 둘째 주문을 마치면 금 $10어치와 황 $15어치가 남는다. 마지막 주문에는 황 $20어치가 필요하므로 가지고 있던 황을 모두 쓰고 창고에서 $5어치를 더 가져온다. 끝나고 나면 금 $13어치와 두꺼비 $2어치, 합쳐서 $15어치가 남는다.

더 나은 순서가 있다. 3, 1, 2 순서로 시전하면 금 $10어치와 황 $15어치, 두꺼비 $2어치를 합쳐 $27어치가 남는다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 주문의 수 $N$과 이 세계에 있는 재료 종류의 수 $M$이 주어진다. 이어지는 $N$개의 줄에는 주문 하나를 나타내는 정수 $M$개가 주어진다. 그중 $j$번째 정수는 $j$번 재료의 값이다. 음수는 그 주문이 소모하는 재료의 달러 비용이고, 양수는 그 주문이 만들어 내는 재료의 달러 가치이며, 0은 그 주문이 소모하지도 만들지도 않는 재료를 뜻한다. 그러므로 한 주문이 같은 재료를 소모하면서 동시에 만들어 낼 수는 없다.

제한

• $1 \le T \le 100$
• $1 \le N \le 100$
• $1 \le M \le 3$
• 주문에 적힌 각 정수는 $-100$ 이상 $100$ 이하이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 테스트 케이스 번호이고 1부터 시작한다. $y$는 Edythe가 마지막에 가질 수 있는 재료 가치의 최댓값이다.