|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|5 초||512 MB||16||10||9||60.000%|
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:
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:
Here's a possible series of events for Ryan:
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
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.
4 2 0 1 0 2 3 2 2 0 0 4 4 1 1 1 5 0 5 0 1 1 1 4 7 5 6
Case #1: 3 Case #2: 3 Case #3: Too Bad Case #4: 6