你刚从家乡搬到了一座大城市！你喜欢新环境的一切，除了食物。你的家乡提供该地区最好的食物（称为“优质食物”），你一定会想念它。

幸运的是，你家乡最大的餐馆提供外卖服务。你可以在一次配送中购买任意数量的食物。无论一次配送中购买了多少食物，配送费都是固定的。

这家餐馆提供不同种类的食物。每种食物有两个属性：单价和保质期。一份“餐”可以供你食用一天；一旦一份餐被吃掉，就不能再吃第二次。某种食物的保质期是指从你收到它开始算起，该食物还可以食用的最大天数。保质期为零意味着你必须在配送当天吃掉这种食物。

在一次配送中，只要你有足够的钱，你可以购买任意多种类的食物，以及每种食物任意数量的餐。注意，如果某种特定食物的保质期为 $t$，那么在一次配送中订购超过 $t+1$ 份该食物是没有意义的：因为至少有一份会在你吃掉它之前过期。

这家餐馆的配送服务非常快，所以你会在购买的当天收到所有食物，并且你可以在当天就吃掉其中的一些。外卖是你获取优质食物的唯一途径。

给定一笔钱，你可以将其用于支付餐费和配送费，请问你最多可以连续多少天每天都吃到优质食物？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例以三个整数 $M$、$F$ 和 $N$ 开头，分别表示你拥有的钱数、配送费以及餐馆提供的食物种类数量。接下来有 $N$ 行，每行包含两个整数 $P_i$ 和 $S_i$，分别表示某种食物的单价和保质期。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是你能每天至少吃一份优质食物的最大天数。

数据范围

$1 \le T \le 50$ $1 \le F \le M$ $1 \le N \le 200$ $1 \le P_i \le M$

子任务 1

$0 \le S_i \le 2,000,000$ $1 \le M \le 2,000,000$

子任务 2

$0 \le S_i \le 10^{18}$ $1 \le M \le 10^{18}$

样例

样例输入 1

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

样例输出 1

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

说明

第一个样例的一种方案是：在城市的第一天购买一份第一种食物和一份第二种食物（总花费 20）。当天吃掉第一种食物，第二天吃掉第二种食物。在第三天，购买一份第一种食物并在当天吃掉。这样总共可以维持三天。