Description

你刚刚从家乡搬到了一座大都市！你喜欢新环境的一切，除了食物。你的家乡是该地区美食的圣地（被称为“优质美食”），你一定会非常怀念。

幸运的是，你家乡最大的一家餐厅提供送餐服务。每次送餐你可以购买任意数量的食物。不论你购买多少食物，每次送餐都需要支付一笔固定的送餐费。

这家餐厅供应多种不同类型的食物。每种食物都有两个属性：每份价格（price-per-meal）和变质时间（time-to-stale）。一份食物可以供你吃一天；吃掉后不能再吃。某种食物的变质时间 $t$ 表示，从你收到食物起，这种食物最多可以保存 $t$ 天。变质时间为 $0$ 意味着你必须在送到当天吃掉。

每次送餐你可以购买任意多种食物，以及每种食物的任意份数，只要你有足够的钱。注意，如果某种食物的变质时间为 $t$，那么在一次送餐中最多只能购买 $t+1$ 份该食物：否则至少有一份会在你吃到之前变质。

这家餐厅送餐速度非常快，所以你当天下单就能收到所有食物，并且可以在当天吃掉部分食物。送餐是你获得优质美食的唯一方式。

给定你拥有的金钱数（可用于购买食物和支付送餐费），你最多能连续多少天每天都吃到至少一份优质美食？

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组数据首先有三个整数 $M$、$F$ 和 $N$，分别表示你拥有的金钱数、每次送餐的费用、以及餐厅提供的食物种类数。接下来 $N$ 行，每行两个整数 $P_i$ 和 $S_i$，分别表示某种食物的每份价格和变质时间。

Output Format

对于每个测试用例，输出一行 "Case #$x$: $y$"，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为你最多能连续多少天每天吃到至少一份优质美食。

3
32 5 2
5 0
10 2
10 10 1
10 10
10 1 1
1 5

Case #1: 3
Case #2: 0
Case #3: 8

Hint

样例说明

以第一个样例为例，你可以在第一天购买第一种食物一份和第二种食物一份（共花费 20 元），第一天吃第一种，第二天吃第二种。第三天再买一份第一种食物当天吃掉。这样共能吃三天。

限制条件

• $1 \leq T \leq 50$
• $1 \leq F \leq M$
• $1 \leq N \leq 200$
• $1 \leq P_i \leq M$

测试集 1（9 分，结果可见）

• $0 \leq S_i \leq 2,\!000,\!000$
• $1 \leq M \leq 2,\!000,\!000$

测试集 2（18 分，结果隐藏）

• $0 \leq S_i \leq 10^{18}$
• $1 \leq M \leq 10^{18}$

翻译由 ChatGPT-4.1 完成。