SP9685 ZTC - Zombie’s Treasure Chest

一些勇敢的战士来到一个失落的村庄。他们很幸运，发现了很多宝藏和一个大宝箱，由于那里有愤怒的僵尸，战士们决定打败僵尸，然后把所有的宝藏带回来。但是战士们发现僵尸是不死的，所向披靡。而且由于宝箱容量的限制，战士们无法通过宝箱携带所有的宝物。事实上，只有两种类型的宝藏: 翡翠和蓝宝石。所有的翡翠在大小和价值上都是相等的，数量是$∞$的。蓝宝石也是。作为拥有神器的战士的牧师: 计算机。现在给定箱子的大小，以及每种宝石的价值和大小，请你计算出我们的战士可以带回来的宝物的最大价值。

有多个测试数据。输入文件的第一行给出了测试数据 $T (T

对于每个测试数据，输出一行包含案例编号和战士可以使用宝箱携带的宝物的最大总价值。