# Zombie’s Treasure Chest

时间限制：1s 空间限制：128MB

### 题目描述

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 long-drawn-out 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.

### 输入格式

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, denoting 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 32-bit signed integers.

### 输出格式

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.

### 样例输入

2 100 1 1 2 2 100 34 34 5 3

### 样例输出

Case #1: 100 Case #2: 86

### 提示

没有写明提示

### 题目来源

Acm 2011 上海