Ryan is playing Kingdom Rush, a singleplayer tower defense game developed by Ironhide Game Studio. In Kingdom Rush, players earn stars by completing levels, in a way described below. Having more stars makes the player more powerful; so while Ryan might not be able to complete level 2 right away, he might be able to complete it after earning stars from level 1.
The real game Kingdom Rush doesn't work in quite the same way as this problem. It isn't important to have played the game in order to solve the problem.
In this problem's version of Kingdom Rush, when a player completes a level, he or she is given a 1star rating or a 2star rating. That rating might allow the player to earn stars as follows:
Ryan might not be able to complete every level right away. For each level, before he can complete it with a 1star rating, he needs to have earned a certain number of stars; and he will need a larger or equal number of stars to complete that level with a 2star rating.
For example, suppose there are two levels:
Ryan is great at tower defense games, but he needs some help to beat Kingdom Rush as quickly as possible. Your job is to figure out how many times he needs to complete levels in order to earn a 2star rating on every level.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing a single integer N, indicating how many levels are in the game. N lines follow. The i
th line contains two integers a_{i} and b_{i}: the number of stars it takes to earn a onestar rating or a twostar rating, respectively, on level i
.
For each test case, output one line containing "Case #x: y", where x
is the case number (starting from 1) and y
is the minimum number of times Ryan must complete levels in order to
have earned a 2star rating on every level. If it is impossible for
Ryan to earn a 2star rating on every level, y
should
instead be the string "Too Bad" (without the " characters, but with that
exact capitalization). This indicates that Ryan is too bad at Kingdom
Rush to finish the whole game.
1 ≤ T ≤ 100.
0 ≤ a_{i} ≤ b_{i} ≤ 2001.
1 ≤ N ≤ 10.
1 ≤ N ≤ 1000.
Input 
Output 
4

Case #1: 3

Kingdom Rush was created by Ironhide Game Studio. Ironhide Game Studio does not endorse and has no involvement with Google Code Jam.
Points  Correct  Attempted 

15pt  1908  3460 
18pt  1616  1844 