你发现了它：制作著名法国菜肴——普罗旺斯炖菜（ratatouille）的终极食谱！你知道制作一份普罗旺斯炖菜需要使用哪些配料，以及每种配料各需要多少克。但你相信任何人都能烹饪，所以你想与世界分享这份食谱……并在此过程中赚点钱！

你订购了一些易于运输的配料包装。每个包装包含一定量的某种配料；即使是同一种配料，不同的包装所含的量也可能不同。为了方便起见，你为每种配料订购了相同数量的包装。

你希望利用这些包装尽可能多地组成普罗旺斯炖菜套件（kit）发送给顾客。一个套件由每种配料各一个包装组成，并附有一个标签，标明该套件可制作的普罗旺斯炖菜份数（整数）。由于你不想亏待顾客或浪费食物，每个包装所含的配料量必须在制作标签上标明的份数所需配料量的 90% 到 110%（含边界值）之间。

例如，假设一份普罗旺斯炖菜需要 500 克番茄和 300 克洋葱。假设你有一个 900 克的番茄包装和一个 660 克的洋葱包装。你可以将它们组成一个可制作两份普罗旺斯炖菜的套件。制作两份需要 1000 克番茄和 600 克洋葱。由于你拥有的 900 克番茄在所需 1000 克番茄的 $[90, 110]\%$ 范围内，且你拥有的 660 克洋葱在所需 600 克洋葱的 $[90, 110]\%$ 范围内，这是可以接受的。然而，你不能说该套件可制作一份或三份普罗旺斯炖菜，也不能说它可制作 1.999 份（份数必须是整数）。

注意，有些包装组合永远无法组成套件。继续使用上面的食谱，例如，如果你有一个 1500 克的番茄包装和一个 809 克的洋葱包装，则无法制作出任何份数的炖菜。三份需要 1500 克番茄和 900 克洋葱，而洋葱的量不在 $[90, 110]\%$ 的范围内。其他任何整数份数也不行。

你希望与尽可能多的顾客分享你的食谱，因此你想要生产出最大数量的有效套件。（当然，每个包装最多只能用于一个套件。）你能组成的套件最大数量是多少？注意，你不需要最大化所制作的普罗旺斯炖菜的总份数。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例包含：

• 一行，包含两个整数 $N$：配料种类数，以及 $P$：每种配料的包装数。
• 一行，包含 $N$ 个整数 $R_i$。第 $i$ 个整数表示制作一份普罗旺斯炖菜所需的第 $i$ 种配料的克数。
• 接下来 $N$ 行，每行包含 $P$ 个整数。第 $i$ 行的第 $j$ 个值 $Q_{ij}$ 表示第 $i$ 种配料的第 $j$ 个包装的重量（以克为单位）。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是你能生产的套件的最大数量。

数据范围

内存限制：1 GB。 $1 \le T \le 100$。 $1 \le R_i \le 10^6$，对于所有 $i$。 $1 \le Q_{ij} \le 10^6$，对于所有 $i$ 和 $j$。

小型数据集（测试集 1 - 可见）

时间限制：60 秒。 $1 \le N \le 2$。 $1 \le P \le 8$。

大型数据集（测试集 2 - 隐藏）

时间限制：120 秒。 $1 \le N \le 50$。 $1 \le P \le 50$。 $N \times P \le 1000$。

样例

样例输入 1

6
2 1
500 300
900
660
2 1
500 300
1500
809
2 2
50 100
450 449
1100 1101
2 1
500 300
300
500
1 8
10
11 13 17 11 16 14 12 18
3 3
70 80 90
1260 1500 700
800 1440 1600
1700 1620 900

样例输出 1

Case #1: 1
Case #2: 0
Case #3: 1
Case #4: 0
Case #5: 3
Case #6: 3

说明

注意，最后一个样例用例不会出现在小型数据集中。

样例 #1 和 #2 是题目描述中提到的例子。

在样例 #3 中，你可以用第一种配料的 450 克包装和第二种配料的 1100 克包装组成一个套件，并称该套件可制作 10 份普罗旺斯炖菜。该份数需要 500 克第一种配料；你有 450 克，这是 500 克的 90%，在允许范围内。它需要 1000 克第二种配料；你有 1100 克，这是 1000 克的 110%，在允许范围内。

然而，一旦你组成了这个套件，你就无法将剩余的包装组成套件。449 克第一种配料和 1101 克第二种配料无法组成 10 份（或任何其他份数）。事实上，(450 g, 1100 g) 套件是这些包装中唯一能组成的套件。

在样例 #4 中，无法组成任何套件。注意，食谱要求按给定顺序使用特定数量的特定配料；配料是不可互换的。毕竟，这是精致的法国菜！

在样例 #5 中，食谱只有一种配料——多么简洁优雅！一份不能超过 11 克，两份不能少于 18 克。可以组成三个套件：两个使用 11 克包装，一个使用 18 克包装。

在样例 #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 份，但只要套件有效，它制作多少份并不重要。