Quality Food (Large)

You just moved from your hometown to a big city. You like everything about the new place except the food. The restaurants back home serve the best food in the region, called quality food, and you already miss it.

The largest restaurant in your hometown delivers. You can buy any amount of food in one delivery, and every delivery costs the same delivery fee $F$ no matter how much food it carries.

The restaurant serves $N$ types of food. Type $i$ has a price per meal $P_i$ and a time to stale $S_i$. One meal feeds you for one day, and a meal that has been eaten cannot be eaten again. The time to stale is the number of days, counted from the day you receive the food, during which that food can still be eaten. If a delivery arrives on day $d$, a meal of type $i$ from it can be eaten on any day from $d$ to $d + S_i$. A time to stale of $0$ means you must eat that food on the day it arrives.

In a single delivery you can buy as many different types, and as many meals of each type, as you have money for. Buying more than $S_i + 1$ meals of type $i$ in one delivery makes no sense: at least one of those meals goes stale before you can eat it.

Delivery is very fast, so everything in one delivery arrives on the day you order it, and you may eat some of it that same day. Delivery is the only way for you to get quality food.

You have $M$ money to spend on meal prices and delivery fees. Find the largest number of days, counted from the day of your first delivery, on which you can eat quality food every single day.

The first line of input gives the number of test cases $T$. Then $T$ test cases follow. The first line of each test case has three integers $M$, $F$ and $N$: the amount of money you have, the delivery fee, and the number of types of food the restaurant serves. The next $N$ lines each hold two integers $P_i$ and $S_i$, the price per meal and the time to stale of one type of food.

Limits

• $1 \le T \le 50$
• $1 \le F \le M \le 10^{18}$
• $1 \le N \le 200$
• $1 \le P_i \le M$
• $0 \le S_i \le 10^{18}$

For each test case, print one line containing "Case #x: y", where $x$ is the test case number starting from 1 and $y$ is the maximum number of days on which you can eat at least one meal of quality food every day.

Here is one way to reach three days in the first test case of the sample. On your first day in the city, order one meal of the first type and one meal of the second type, which costs 20 including the fee. Eat the first type that day and the second type the next day. On the third day, order one meal of the first type again and eat it the same day.