Ryan is playing Kingdom Rush, a single-player 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 1-star rating or a 2-star 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 1-star 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 2-star 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 2-star 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
ith line contains two integers ai and bi: the number of stars it takes to earn a one-star rating or a two-star rating, respectively, on level
For each test case, output one line containing "Case #x: y", where
x is the case number (starting from 1) and
is the minimum number of times Ryan must complete levels in order to
have earned a 2-star rating on every level. If it is impossible for
Ryan to earn a 2-star rating on every level,
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 ≤ ai ≤ bi ≤ 2001.
1 ≤ N ≤ 10.
1 ≤ N ≤ 1000.
Kingdom Rush was created by Ironhide Game Studio. Ironhide Game Studio does not endorse and has no involvement with Google Code Jam.