Zombie's Treasure Chest#3085
Some brave warriors arrived at a lost village. They were very lucky to find a lot of treasures and a large treasure chest, but also encountered angry zombies.
The warriors were so brave that they decided to defeat the zombies and take all the treasures. After a long and grueling battle lasting from morning to night, the warriors realized that the zombies are undead and invincible.
Of course, the treasures should not be left here. Unfortunately, the warriors cannot carry all the treasures away because of the limited capacity of the chest. There are only two types of treasures: emeralds and sapphires. All emeralds are identical in size and value, and available in infinite quantity. The same applies to sapphires.
As the priest of the warriors, possessing a magic artifact—a computer—and knowing the chest's capacity, as well as the size and value of each type of gem, you must calculate the maximum value of treasures the warriors can carry.
The first line contains the number of test cases (t \leq 200). Each test case is given in a separate line and consists of five integers , s_1, v_1, s_2, v_2, where is the capacity of the chest, s_1 and v_1 are the size and value of an emerald, and s_2 and v_2 are the size and value of a sapphire. All values are positive integers and fit in a -bit signed integer.
For each test case, output a single line containing the maximum value of treasures that can be carried with the chest.
Example 1