P13163 [GCJ 2017 #1A] Ratatouille

你发现了终极的“ratatouille”（法国蔬菜杂烩）配方！你已经知道制作一份 ratatouille 需要哪些原料，以及每种原料需要多少克。你相信“人人都能做菜”，所以你想把这个配方分享给全世界……顺便赚点钱！ 你订购了一些便于运输的原料包装。每个包装只包含一种原料；即使是同一种原料，不同包装中的数量也可能不同。为了方便，你为每种原料都订购了相同数量的包装。 你希望用这些包装尽可能多地组装出 ratatouille 套装，发给顾客。每个套装由每种原料各一个包装组成，并贴有一个标签，标明该套装可以制作多少份 ratatouille（份数为整数）。为了保证不亏待顾客且不浪费食材，每个包装中的原料含量必须在制作标签上标明的份数所需原料的 $90\%$ 到 $110\%$（含端点）之间。 例如，假设制作一份 ratatouille 需要 $500$ 克番茄和 $300$ 克洋葱。假如你有一个 $900$ 克的番茄包装和一个 $660$ 克的洋葱包装。你可以将它们组合成一个可以制作两份 ratatouille 的套装。制作两份需要 $1000$ 克番茄和 $600$ 克洋葱。你拥有的 $900$ 克番茄在 $1000$ 克的 $[90\%, 110\%]$ 区间内，$660$ 克洋葱也在 $600$ 克的 $[90\%, 110\%]$ 区间内，因此这是可行的。然而，你不能说这个套装可以制作一份或三份 ratatouille，也不能说可以制作 $1.999$ 份（份数必须为整数）。 注意，有些包装组合永远无法组成一个套装。继续上面的例子，如果你有一个 $1500$ 克的番茄包装和一个 $809$ 克的洋葱包装，无论制作多少份都不行。三份需要 $1500$ 克番茄和 $900$ 克洋葱，但 $809$ 克洋葱不在 $[90\%, 110\%]$ 区间内。没有其他整数份数可行。 你希望让尽可能多的顾客享受到你的配方，所以你想制作最多数量的有效套装。（当然，每个包装最多只能用在一个套装中。）你最多能组装出多少个套装？注意，你不需要最大化 ratatouille 的总份数。

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据包括： - 一行包含两个整数 $N$ 和 $P$，分别表示原料种类数和每种原料的包装数量。 - 一行包含 $N$ 个整数 $R_i$，第 $i$ 个数表示制作一份 ratatouille 需要的第 $i$ 种原料的克数。 - 接下来 $N$ 行，每行包含 $P$ 个整数。第 $i$ 行的第 $j$ 个数 $Q_{ij}$ 表示第 $i$ 种原料的第 $j$ 个包装的克数。

对于每组测试数据，输出一行 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是你最多能组装出的套装数量。

**样例解释** 注意，最后一个样例不会出现在 Small 数据集中。 样例 1 和 2 就是题目描述中的例子。 在样例 3 中，你可以用第一种原料的 $450$ 克包装和第二种原料的 $1100$ 克包装，组装成一个制作 $10$ 份 ratatouille 的套装。制作 $10$ 份需要第一种原料 $500$ 克，你有 $450$ 克，正好是 $500$ 克的 $90\%$，在允许范围内。第二种原料需要 $1000$ 克，你有 $1100$ 克，正好是 $110\%$，也在允许范围内。 但组装完这个套装后，剩下的包装无法再组成套装。$449$ 克的第一种原料和 $1101$ 克的第二种原料无法组成 $10$ 份（或其他份数）的套装。实际上，($450$ 克, $1100$ 克) 是唯一能组成的套装。 在样例 4 中，无法组成任何套装。注意，配方要求每种原料的顺序和用量都不能变，原料不可互换。这可是正宗法式料理！ 在样例 5 中，配方只有一种原料——多么优雅！一份不能超过 $11$ 克，两份不能少于 $18$ 克。可以组装出三个套装：两个 $11$ 克包装，一个 $18$ 克包装。 在样例 6 中，可以组装出三个有效套装：($700$ 克, $800$ 克, $900$ 克)，可制作 $10$ 份；($1500$ 克, $1600$ 克, $1700$ 克) 和 ($1260$ 克, $1440$ 克, $1620$ 克)，每个都可制作 $20$ 份。注意，($1260$ 克, $1440$ 克, $1620$ 克) 也可以标为 $17$、$18$ 或 $19$ 份，但只要套装有效，份数具体是多少并不重要。 **数据范围** - $1 \leq T \leq 100$。 - $1 \leq R_i \leq 10^6$，对所有 $i$。 - $1 \leq Q_{ij} \leq 10^6$，对所有 $i, j$。 **小数据集（12 分，测试点 1 - 可见）** - 时间限制：15 秒。 - $1 \leq N \leq 2$。 - $1 \leq P \leq 8$。 **大数据集（23 分，测试点 2 - 隐藏）** - 时间限制：30 秒。 - $1 \leq N \leq 50$。 - $1 \leq P \leq 50$。 - $N \times P \leq 1000$。 由 ChatGPT 4.1 翻译