The Crazy O2jamer
O2jam is a famous music game. In this game, the player will listen to the music, and many notes will appear on the screen and fall down from the top. When the notes move to the line on the botton of the screen, the player should press the correct keys just on time, and the system will judge your rate and give scores. Sometimes there are some long notes, the player should hold the key down from the beginning and leave from the end, the system will judge one long note as two notes. The notes’ falling speed has some relationship with the the speed of music(BPM, beat per minute). If the player has a good feeling of the music’s beat, his rate will be very high and he will get high scores. Different music has different levels. When the chosen level is very high, the form of the notes will be very strong, and the player will “die” in the game soon if he has not enough skill.
When you beat a note, you may get a “COOL” or a “GOOD”, but if you miss one, you’ll get a “MISS”. every “COOL” will give you 200 scores, and every “GOOD” will give 100. The game also have JAMs and COMBO. When you get a “COOL”, you’ll also get 1/25 JAM, and every “GOOD” will give you 1/50 JAM. After you get one JAM or more, every JAM will add extra 10 scores to every “COOL” and 5 to every “GOOD”, so JAMs is very important for getting scores.
If you beat notes incessantly, you will get COMBO. 2 notes will be 2 COMBO, 3 notes will be 3 COMBO, and so on. But, if you miss one note, the COMBO will back to zero, and all the JAMs you have will be lost.
For example, you get 45 “COOL”s, 65 “GOOD”s, then 1 “MISS”, then 38 “COOL”s, the scores will be 200*25+210*20+105*10+110*50+115*5+200*25+210*13=24055.
Now, Dreamwind will play this game in another style. He wants to get s scores in a game that have n notes (and of course he can get more scores), and let the maximum number of COMBO as small as possible. However, Dreamwind knows he can get at most c “COOL”s during this game, but he can control himself freely to get “GOOD”s and “MISS”s. Can you help him to find out the smallest MAX COMBO he can get?
5 5 750 5 5 900 6 3 700 10 0 1002 50 30 7982
2 5 2 impossible 37