Zombie's Treasure Chest

A band of brave warriors reaches a lost village. They are lucky enough to find piles of treasure and a large treasure chest, but also a horde of angry zombies.

The warriors decide to defeat the zombies and haul all the treasure home. After a brutal battle that lasts from morning until night, they discover that the zombies are undead and cannot be killed.

Still, the treasure cannot be left behind. The catch is that the chest has limited capacity, so not every gem can be taken. There are only two kinds of treasure: emeralds and sapphires. Every emerald has the same size and value, and there is an unlimited supply of them; the same holds for sapphires.

Given the capacity $N$ of the chest and the size and value of each kind of gem, compute the maximum total value the warriors can carry away. Formally, choose non-negative integers $x$ and $y$ with $x \cdot S_1 + y \cdot S_2 \le N$ that maximize $x \cdot V_1 + y \cdot V_2$.

The first line contains the number of test cases $T$ ($T \le 200$).

Each test case is a single line with five integers $N, S_1, V_1, S_2, V_2$: the capacity $N$ of the chest, the size $S_1$ and value $V_1$ of one emerald, and the size $S_2$ and value $V_2$ of one sapphire. All integers are positive and fit in a signed 32-bit integer.

For each test case, print one line with the case number and the maximum total value of treasure that can be carried in the chest. Use the format Case #k: value, where $k$ is the test case number starting from 1.