라따뚜이

당신은 마침내 유명한 프랑스 요리 라따뚜이의 궁극적인 조리법을 발견했다! 라따뚜이 한 인분을 만들기 위해 어떤 재료를 사용해야 하는지, 그리고 각 재료를 몇 그램씩 사용해야 하는지 알고 있다. 하지만 당신은 누구나 요리할 수 있다고 믿기에 이 조리법을 세상과 공유하고 싶으며... 그 과정에서 돈도 조금 벌고 싶다!

당신은 배송하기 쉬운 재료 포장 몇 개를 주문했다. 각 포장에는 한 가지 재료가 일정량 들어 있으며, 같은 재료가 들어 있더라도 서로 다른 포장에는 양이 다르게 들어 있을 수 있다. 편의를 위해 각 재료의 포장 수는 똑같이 주문했다.

이 포장들로 가능한 한 많은 라따뚜이 키트를 만들어 고객에게 보내고 싶다. 하나의 키트는 각 재료의 포장을 정확히 하나씩 포함하며, 그 키트로 만들 수 있는 라따뚜이의 정수 인분 수가 적힌 라벨도 포함한다. 고객에게 실제보다 적게 제공하거나 음식을 낭비하고 싶지 않으므로, 각 포장에는 키트 라벨에 적힌 인분 수의 라따뚜이를 실제로 만드는 데 필요한 해당 재료 양의 90퍼센트 이상 110퍼센트 이하가 들어 있어야 한다.

예를 들어 라따뚜이 한 인분에 토마토 500 g과 양파 300 g이 필요하다고 하자. 토마토 900 g 포장과 양파 660 g 포장이 있다고 하자. 이들을 라따뚜이 두 인분을 만드는 키트로 구성할 수 있다. 두 인분을 만들려면 토마토 1000 g과 양파 600 g이 필요하다. 가지고 있는 토마토 900 g은 필요한 토마토 1000 g의 $[90, 110]$% 이내이고, 가지고 있는 양파 660 g은 필요한 양파 600 g의 $[90, 110]$% 이내이므로 허용된다. 하지만 이 키트로 라따뚜이 한 인분이나 세 인분을 만들 수 있다고 할 수는 없으며, 1.999인분을 만들 수 있다고 할 수도 없다(인분 수는 정수여야 한다).

키트를 절대로 구성할 수 없는 포장 조합도 있다는 점에 유의하라. 위의 조리법을 계속 사용하여, 예를 들어 토마토 1500 g 포장과 양파 809 g 포장이 있다면 만들 수 있는 인분 수가 없다. 세 인분에는 토마토 1500 g과 양파 900 g이 필요하지만, 양파의 양이 $[90, 110]$% 범위 내에 있지 않다. 다른 어떤 정수 인분 수도 조건을 만족하지 않는다.

가능한 한 많은 고객과 조리법을 공유하고 싶으므로 유효한 키트를 최대한 많이 만들고자 한다. (물론 각 포장은 최대 하나의 키트에만 사용할 수 있다.) 구성할 수 있는 키트 수의 최댓값은 얼마인가? 만들어지는 라따뚜이의 총 인분 수를 최대화할 필요는 없다는 점에 유의하라.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 모든 i에 대해 1 ≤ $R_{i}$ ≤ $10^{6}$. 모든 i와 j에 대해 1 ≤ $Q_{ij}$ ≤ $10^{6}$.

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 60초. 1 ≤ N ≤ 2. 1 ≤ P ≤ 8.

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 120초. 1 ≤ N ≤ 50. 1 ≤ P ≤ 50. N × P ≤ 1000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 다음과 같이 구성된다.

• 한 줄에 두 정수 N과 P가 주어진다. N은 재료의 수이고 P는 각 재료의 포장 수이다.

• 한 줄에 N개의 정수 $R_{i}$가 주어진다. 이 중 i번째 값은 라따뚜이 한 인분을 만드는 데 필요한 i번째 재료의 그램 수를 나타낸다.

• 이어지는 N개의 줄에는 각각 P개의 정수가 주어진다. 이 줄들 중 i번째 줄의 j번째 값 $Q_{ij}$는 i번째 재료의 j번째 포장에 들어 있는 양을 그램 단위로 나타낸다.

각 테스트 케이스마다 Case #x: y을 한 줄에 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y은 위에서 설명한 대로 만들 수 있는 키트 수의 최댓값이다.

마지막 예제 케이스는 작은 데이터 세트에는 등장하지 않는다는 점에 유의하라.

예제 케이스 #1와 #2는 문제 설명에서 다룬 케이스들이다.

예제 케이스 #3에서는 첫 번째 재료의 450 g 포장과 두 번째 재료의 1100 g 포장으로 키트를 구성하고, 이 키트가 라따뚜이 10인분을 만든다고 할 수 있다. 이 인분 수에는 첫 번째 재료 500 g이 필요하다. 가지고 있는 양은 450 g으로, 500의 90%이며 허용 범위 내에 있다. 두 번째 재료는 1000 g이 필요하다. 가지고 있는 양은 1100 g으로, 1000의 110%이며 허용 범위 내에 있다.

그러나 이 키트를 구성하고 나면 남은 포장들로는 키트를 구성할 수 없다. 첫 번째 재료 449 g과 두 번째 재료 1101 g으로는 10인분도, 그 밖의 어떤 인분 수도 만들 수 없다. 실제로 (450 g, 1100 g) 키트가 이 포장들로 구성할 수 있는 유일한 키트이다.

예제 케이스 #4에서는 어떤 키트도 구성할 수 없다. 조리법에는 주어진 순서대로 특정 재료가 특정 양만큼 필요하며, 재료들은 서로 바꿔 쓸 수 없다는 점에 유의하라. 결국 이것은 제대로 된 프랑스 고급 요리이기 때문이다!

예제 케이스 #5에서 조리법에는 재료가 단 하나뿐이다. 정말 우아할 정도로 간단하다! 한 인분에는 11 g보다 많이 사용할 수 없고, 두 인분에는 18 g보다 적게 사용할 수 없다. 세 개의 키트를 구성할 수 있다. 두 개는 각각 11 g 포장으로, 하나는 18 g 포장으로 구성한다.

예제 케이스 #6에서는 유효한 키트 세 개를 구성할 수 있다. (700 g, 800 g, 900 g)은 10인분을 만들고, (1500 g, 1600 g, 1700 g)과 (1260 g, 1440 g, 1620 g)은 각각 20인분을 만든다. 또한 (1260 g, 1440 g, 1620 g) 키트가 17, 18, 또는 19인분을 만든다고 할 수도 있지만, 키트가 유효하기만 하면 키트 하나가 몇 인분을 만드는지는 중요하지 않다는 점에 유의하라.