ZTC  Zombie’s Treasure Chest
Some brave warriors come to a lost village. They are very lucky and find a lot of treasures and a big treasure chest, but with angry zombies.
The warriors are so brave that they decide to defeat the zombies and then bring all the treasures back. A brutal longdrawnout battle lasts from morning to night and the warriors find the zombies are undead and invincible.
Of course, the treasures should not be left here. Unfortunately, the warriors cannot carry all the treasures by the treasure chest due to the limitation of the capacity of the chest. Indeed, there are only two types of treasures: emerald and sapphire. All of the emeralds are equal in size and value, and with infinite quantities. So are sapphires.
Being the priest of the warriors with the magic artifact: computer, and given the size of the chest, the value and size of each types of gem, you should compute the maximum value of treasures our warriors could bring back.
Input
There are multiple test cases. The number of test cases T (T <= 200) is given in the first line of the input file. For each test case, there is only one line containing five integers N, S1, V1, S2, V2.It means the size of the treasure chest is N and the size and value of an emerald is S1 and V1, size and value of a sapphire is S2, V2. All integers are positive and fit in 32bit signed integers.
Output
For each test case, output a single line containing the case number and the maximum total value of all items that the warriors can carry with the chest.
Example
Input: 2 100 1 1 2 2 100 34 34 5 3 Output: Case #1: 100 Case #2: 86
This problem is first solved by team Windrunner (Tsinghua University) at 32 minutes after the onsite contest starts. (They have 1 wrong try before they get Accepted.)
hide comments
[Rampage] Blue.Mary:
20111022 03:37:50
The constraints are 32bit signed integer,i.e. 2^311. Don't you see that? Think of another solution. DP is obviously not the case. 

RAJDEEP GUPTA:
20111021 18:08:38
I am using DP with bottom up approach. But getting SIGSEGV!!! :( Is this occurring because I am allocating memory at run time depending upon the value of n? Last edit: 20111021 18:14:16 
Added by:  Fudan University Problem Setters 
Date:  20111010 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  ACM/ICPC Regional Contest, Shanghai 2011; Problem Setter: g201513 