12397번 - Kingdom Rush (Large) 다국어

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:

• If the player has never completed the level before and completes it with a 1-star rating, that player earns 1 star.
• If the player has never completed the level before and completes it with a 2-star rating, that player earns 2 stars.
• If the player has only completed the level before with a 1-star rating and completes it this time with a 2-star rating, the player earns 1 more star.

Otherwise there is no way for a player to earn stars.

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:

• Level 1 requires 0 stars to complete with a 1-star rating, and 1 star to complete with a 2-star rating.
• Level 2 requires 0 stars to complete with a 1-star rating, and 2 stars to complete with a 2-star rating.

Here's a possible series of events for Ryan:

1. Ryan starts with 0 stars. He can choose to complete either level 1 or level 2 with a 1-star rating. He chooses to complete level 1 with a 1-star rating. Now he has 1 star.
2. Now Ryan can either complete level 2 with a 1-star rating, or level 1 with a 2-star rating. He chooses to complete level 1 with a 2-star rating. Now he has 2 stars.
3. Now Ryan can complete level 2 with a 2-star rating. He does that, and now he has 4 stars.
4. Now he is done, having completed all levels with 2-star ratings and earned 4 stars (2 per level). He has completed levels 3 times: level 1 twice, and level 2 once.

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 a_i and b_i: the number of stars it takes to earn a one-star rating or a two-star rating, respectively, on level i.

Limits

• 1 ≤ T ≤ 100.
• 0 ≤ a_i ≤ b_i ≤ 2001.
• 1 ≤ N ≤ 1000.

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 2-star rating on every level. If it is impossible for Ryan to earn a 2-star 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.