멀린 QA

에디스는 마법 주문 공장인 멀린 주식회사의 품질 보증 부서에서 일하는 젊은 마법사이다. 그녀의 일은 멀린이 직접 발명한 마법 주문을 시험하는 것이다. 각 주문은 특정 재료를 정확한 양만큼 필요로 하며, 이를 다른 재료의 다른 양으로 변환한다. 에디스의 일은 주문이 올바르게 작동하는지 확인하기 위해 각 주문을 정확히 한 번씩 시전하는 것이다.

그녀는 필요한 각 재료를 필요한 양만큼 가지고 있을 때만 주문을 시전할 수 있다. 이전 주문으로 올바른 종류의 재료를 이미 만들어 두었다면, 에디스는 반드시 그것부터 사용해야 한다. 하지만 재료가 여전히 더 필요하다면 멀린의 창고에서 가져올 수 있다. 처음에는 아무 재료도 가지고 있지 않지만, 마지막에는 자신이 만들고 사용하지 않은 여분의 재료를 모두 가질 수 있다.

에디스는 견습 기간에 가능한 한 많은 이익을 얻고 싶어 한다! 주어진 N개의 각 주문을 정확히 한 번씩 시전해야 하지만, 어떤 순서로 시전해도 된다. 각 주문이 예상대로 작동한다고 할 때, 마지막에 가장 많은 돈을 벌 수 있는 순서는 무엇인가?

예를 들어, 시험 계획에 다음과 같은 3개의 주문이 있다고 하자.

• 입력: 금 $7어치. 출력: 황 $5어치.

• 입력: 없음. 출력: 금 $10어치, 황 $10어치.

• 입력: 금 $3어치, 황 $20어치. 출력: 두꺼비 $2어치. 첫 번째 주문은 금을 황으로 변환하고, 두 번째 주문은 아무것도 없는 상태에서 금과 황을 만들어 내며, 세 번째 주문은 금과 황을 두꺼비로 변환한다.

에디스가 이 주문들을 1, 2, 3 순서로 시전한다면, 먼저 주문 #1을 위해 창고에서 금 $7어치를 가져올 것이다. 그러면 주문 #1과 주문 #2을 시전할 수 있고, 금 $10어치와 황 $15어치를 얻게 된다. 마지막 주문에는 금 $3어치와 황 $20어치가 필요하다. 지금까지 만든 황 전부와 금 $3어치, 그리고 창고에서 가져온 황 $5어치를 더 사용해야 한다. 그러면 마지막에 총 $9어치의 재료가 남는다(금 $7어치와 두꺼비 $2어치).

하지만 더 좋은 계획이 있다. 주문을 3, 1, 2 순서로 시전하면 마지막에 총 $27어치의 재료를 갖게 된다(금 $10어치, 황 $15어치, 두꺼비 $2어치).

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ N ≤ 100. -100 ≤ 각 주문의 각 정수는 ≤ 100.

소규모 데이터 세트

시간 제한: 240초. 1 ≤ M ≤ 2.

대규모 데이터 세트

시간 제한: 480초. 1 ≤ M ≤ 8.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 N과 M이 포함된 한 줄로 시작한다. M은 세상에 존재하는 재료 종류의 수이다. 다음 N개의 각 줄에는 주문을 설명하는 M개의 정수가 주어진다. 각 정수는 해당 재료의 가치(또는 비용)이다. 음의 정수는 입력 재료의 달러 비용이고, 양의 정수는 출력 재료의 달러 가치이며, 영은 해당 주문에서 생산되지도 소비되지도 않는 재료를 나타낸다. 이는 어떤 주문도 같은 재료를 동시에 소비하고 생산할 수 없음을 뜻하기도 한다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), y는 에디스가 마지막에 가질 수 있는 재료 가치의 최댓값이다.