Attack

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

PBH 最近在玩一个游戏。游戏中玩家有 100 的血量,目前有 n 个小怪,小怪会按顺序前来攻击玩家且小怪只会采用 1v1 的方式,玩家每次可秒杀一个小怪,并受到小怪攻击力的伤害(血量减少小怪攻击力的数值),打死小怪会掉落药水。

现在问题来了,打完这 n 个小怪最少需要喝多少瓶药水(喝药水不耗时)?

Input

先输入一个整数 t 表示数据的组数,t 不超过 1000。

对于每组数据,第一行先输入小怪的个数 n (1 <= n <= 100),接下来的 n 行输入小怪攻击力 atki (1 <= atki <= 50) 以及小怪掉落 mi (0 <= mi <= 4) 个药水和药水所能恢复生命的值 ai (1 <= ai <= 30)。

Output

对于每组数据先输出 "Case #x: ",x 表示当前为第几组数据,之后输出打完所有小怪需要的最少药水数。如果无法杀死这 n 个小怪,即某次攻击小怪时已无药水可用且当前血量无法攻击小怪(小怪攻击大于等于当前血量),则输出 ”QAQ”。

所有输出均不包括引号。

Sample Input

3
2
50 1 20
49 0
4
50 1 10
40 0
30 3 20 30 20
10 0
3
50 3 20 15 1
45 2 1 1
27 0

Sample Output

Case #1: 0
Case #2: QAQ
Case #3: 2

Hint

请大家仔细核对 "Case #x: ",建议复制样例输出中的字符串到你的代码,以防敲错导致 Wrong Answer。

Source

【2016级《程序设计基础(B)II》期末上机考试-第二场】MLE_kenan