라따뚜이 (라지)

문제

라따뚜이 조리법을 알고 있다. 어떤 재료가 들어가는지, 한 그릇에 각 재료가 몇 그램 필요한지도 안다. 이 조리법을 키트로 만들어 팔려고 한다.

배송하기 좋은 재료 꾸러미를 주문했다. 꾸러미 하나에는 재료 한 종류만 들어 있고, 같은 재료라도 꾸러미마다 들어 있는 양이 다를 수 있다. 재료마다 꾸러미를 같은 개수씩 주문했다.

키트 하나에는 재료마다 꾸러미를 정확히 하나씩 담고, 몇 인분인지 적은 정수 라벨을 붙인다. 손님에게 모자라게 주지도 않고 재료를 버리지도 않으려면, 키트에 담긴 꾸러미는 라벨에 적힌 인분을 만드는 데 필요한 그 재료 양의 90퍼센트 이상 110퍼센트 이하를 담고 있어야 한다.

한 그릇에 토마토 500그램과 양파 300그램이 필요하고, 토마토 900그램 꾸러미와 양파 660그램 꾸러미가 있다고 하자. 이 둘로 2인분 라벨을 붙인 키트를 만들 수 있다. 2인분에는 토마토 1000그램과 양파 600그램이 필요한데, 900그램은 1000그램의 90퍼센트에서 110퍼센트 사이이고 660그램은 600그램의 90퍼센트에서 110퍼센트 사이다. 같은 두 꾸러미에 1인분이나 3인분 라벨은 붙일 수 없고, 인분 수는 정수여야 하므로 1.999인분 라벨도 붙일 수 없다.

어떤 라벨도 붙일 수 없는 꾸러미 조합도 있다. 같은 조리법에서 토마토 1500그램 꾸러미와 양파 809그램 꾸러미를 보자. 3인분에는 토마토 1500그램과 양파 900그램이 필요한데 양파 809그램은 허용 범위에 못 미치고, 다른 어떤 정수 인분도 조건을 맞추지 못한다.

꾸러미 하나는 많아야 키트 하나에 들어간다. 만들 수 있는 키트 개수의 최댓값을 구하라. 총 인분 수까지 최대로 만들 필요는 없다.

입력

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어서 $T$ 개의 테스트 케이스가 다음 형식으로 주어진다.

첫 줄에 재료의 개수 $N$ 과 재료마다 가진 꾸러미의 개수 $P$ 가 주어진다.
다음 줄에 정수 $N$ 개 $R_i$ 가 주어진다. $i$ 번째 값은 $i$ 번 재료가 한 그릇에 몇 그램 필요한지를 나타낸다.
다음 $N$ 개의 줄에 정수가 $P$ 개씩 주어진다. $i$ 번째 줄의 $j$ 번째 값 $Q_{ij}$ 는 $i$ 번 재료의 $j$ 번째 꾸러미에 들어 있는 양이며, 단위는 그램이다.

제한:

$1 \le T \le 100$
$1 \le N \le 50$
$1 \le P \le 50$
$N \times P \le 1000$
모든 $i$ 에 대해 $1 \le R_i \le 10^6$
모든 $i$ 와 $j$ 에 대해 $1 \le Q_{ij} \le 10^6$

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 만들 수 있는 키트 개수의 최댓값이다.

힌트

예제의 첫 번째와 두 번째 테스트 케이스는 문제에서 설명한 상황이다.

세 번째 테스트 케이스에서는 첫 번째 재료의 450그램 꾸러미와 두 번째 재료의 1100그램 꾸러미로 10인분 라벨을 붙인 키트를 만들 수 있다. 10인분에는 첫 번째 재료가 500그램 필요한데 450그램은 그 90퍼센트이고, 두 번째 재료가 1000그램 필요한데 1100그램은 그 110퍼센트다. 남은 449그램 꾸러미와 1101그램 꾸러미에는 어떤 라벨도 붙일 수 없으므로 키트는 하나가 최대다.

네 번째 테스트 케이스에서는 키트를 하나도 만들지 못한다. 조리법은 재료마다 필요한 양을 주어진 순서대로 정해 두며, 재료끼리 바꿔 쓰지 못한다.

다섯 번째 테스트 케이스의 조리법에는 재료가 하나뿐이다. 1인분은 11그램을 넘게 쓰지 못하고, 2인분은 18그램보다 적게 쓰지 못한다. 11그램 꾸러미로 두 개, 18그램 꾸러미로 하나, 모두 세 개의 키트를 만들 수 있다.

여섯 번째 테스트 케이스에서는 키트를 세 개 만들 수 있다. (700그램, 800그램, 900그램)은 10인분이고, (1500그램, 1600그램, 1700그램)과 (1260그램, 1440그램, 1620그램)은 각각 20인분이다. (1260그램, 1440그램, 1620그램)에는 17인분, 18인분, 19인분 라벨을 붙여도 된다. 키트가 유효하기만 하면 라벨의 숫자는 상관없다.