Zombie’s Treasure Chest

一些勇敢的战士来到了一座失落的村庄。他们非常幸运，找到了大量的财宝和一个巨大的宝箱，但同时也遇上了愤怒的僵尸。

战士们非常勇敢，他们决定先打败僵尸，再把所有财宝带回去。一场残酷的战斗从清晨持续到夜晚，战士们才发现这些僵尸不死不灭、无法战胜。

当然，财宝不能就这样留在这里。可惜受宝箱容量的限制，战士们没办法把所有财宝都装走。所幸财宝只有两种：绿宝石和蓝宝石。所有绿宝石的体积和价值都相同，且数量无限；蓝宝石也是如此。

你是战士们的祭司，掌握着「计算机」这件神器。给定宝箱的容量以及每种宝石的体积和价值，请你计算战士们能带回的财宝的最大总价值。

输入格式

输入包含多组测试数据，第一行是数据组数 $T$。

每组数据一行，包含五个整数 $N, S_1, V_1, S_2, V_2$，其中 $N$ 为宝箱的容量，$S_1$ 和 $V_1$ 为一块绿宝石的体积和价值，$S_2$ 和 $V_2$ 为一块蓝宝石的体积和价值。

输出格式

对于每组数据，输出一行，包含数据编号和战士们用宝箱能带走的物品的最大总价值，格式见样例输出。

样例输入

2
100 1 1 2 2
100 34 34 5 3

样例输出

Case #1: 100
Case #2: 86

样例解释

第一组数据中两种宝石的单位体积价值都是 $1$，把容量为 $100$ 的宝箱装满即可得到价值 $100$。

第二组数据中取 $2$ 块绿宝石（体积 $68$，价值 $68$）和 $6$ 块蓝宝石（体积 $30$，价值 $18$），共占体积 $98$，总价值为 $68+18=86$。

数据范围

• $T\le 200$；
• 所有整数均为正数，且都在 $32$ 位有符号整数范围内。

来源与许可

本题为「Zombie's Treasure Chest」，题面与测试数据整理自 BZOJ 2490。

样例 1

输入

2
100 1 1 2 2
100 34 34 5 3

输出

Case #1: 100
Case #2: 86