Quality Food

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 below, and you miss it.

The largest restaurant in your hometown delivers. You can buy any amount of food in one delivery. Every delivery costs a fixed delivery fee, and that fee is the same no matter how much food the delivery contains.

The restaurant serves several types of food. Each type has a price per meal and a time to stale. One meal feeds you for one day, and a meal that has been eaten cannot be eaten again. If a type has a time to stale of $t$, you can still eat it up to day $t$, counting the day you received it as day 0. A time to stale of 0 means you must eat that type on the day it is delivered.

In one delivery you can buy as many different types, and as many meals of each type, as your money allows. If a type has a time to stale of $t$, ordering more than $t + 1$ meals of it in one delivery is pointless: at least one meal goes stale before you can eat it.

Delivery is very fast, so you receive everything on the day you buy it, and you may eat some of it that same day. Delivery is the only way to get quality food.

You spend your money on meal prices and delivery fees. Find the largest number of days, counted from day 1 with no gap, on which you can eat quality food.

The first line contains the number of test cases $T$. Each test case begins with a line of three integers $M$, $F$ and $N$: the amount of money you have, the delivery fee, and the number of food types the restaurant serves. $N$ lines follow, and the $i$-th of them contains two integers $P_i$ and $S_i$, the price per meal and the time to stale of that type.

Limits

• $1 \le T \le 50$
• $1 \le F \le M$
• $1 \le N \le 200$
• $1 \le P_i \le M$
• $0 \le S_i \le 2\,000\,000$
• $1 \le M \le 2\,000\,000$

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

The first case of the first example can be covered for 3 days like this. On your first day in the city, buy one meal of the first type and one meal of the second type (20 in total, delivery fee included). Eat the first type that day and the second type the next day. On the third day, buy one meal of the first type again and eat it that day.