题目描述

一些勇敢的战士来到一个没落的村庄。他们非常幸运，发现了藏在村庄里的宝藏和一个容量为 $N$ 的宝箱，但愤怒的僵尸发现了他们。

战士们十分勇猛，他们决定打败僵尸，然后带回所有的宝藏。一场残酷又旷日持久的战斗打响了，逐渐，战士们发现了一个问题 ： 僵尸们是无敌的，永生的。

当然，战士们也不会把宝藏留在这里。不幸的是，宝箱的容量是有限的，战士们无法带走所有的宝藏。事实上，只有两种类型的宝藏 ： 祖母绿和蓝宝石。所有的祖母绿和蓝宝石的数量都是无限的。

作为拥有魔法神器的祭司：计算机，应考虑箱子的大小，每种宝石的价值和大小，你应当计算出战士们可以带回的宝藏的最大价值 。

输入格式

本题有 $T$ 个测试用例。第一行一个正整数 $T$ $(T\le200)$ 。对于每个测试用例，只有一行，包含五个整数 $N,S_1,V_1,S_2,V_2$ 。$N$ 表示宝箱的大小，$S_1$ 和 $V_1$ 分别表示祖母绿的大小和价值，蓝宝石的大小和价值分别是 $S_2$ 和 $V_2$ 。所有的整数都是正数，且不超过 $int$ 的范围。

输出格式

对于每个测试用例，输出一行，其中包含用例编号和战士可以随身携带的所有物品的最大总价值 。

---

---

源代码：

### 题目描述

一些勇敢的战士来到一个没落的村庄。他们非常幸运，发现了藏在村庄里的宝藏和一个容量为 $N$ 的宝箱，但愤怒的僵尸发现了他们。

战士们十分勇猛，他们决定打败僵尸，然后带回所有的宝藏。一场残酷又旷日持久的战斗打响了，逐渐，战士们发现了一个问题 ： 僵尸们是无敌的，永生的。

当然，战士们也不会把宝藏留在这里。不幸的是，宝箱的容量是有限的，战士们无法带走所有的宝藏。事实上，只有两种类型的宝藏 ： 祖母绿和蓝宝石。所有的祖母绿和蓝宝石的数量都是无限的。

作为拥有魔法神器的祭司：计算机，应考虑箱子的大小，每种宝石的价值和大小，你应当计算出战士们可以带回的宝藏的最大价值 。

### 输入格式 

本题有 $T$ 个测试用例。第一行一个正整数 $T$ $ (T\le200)$ 。对于每个测试用例，只有一行，包含五个整数 $N,S_1,V_1,S_2,V_2$ 。$N$ 表示宝箱的大小，$S_1$ 和 $V_1$ 分别表示祖母绿的大小和价值，蓝宝石的大小和价值分别是 $S_2$ 和 $V_2$ 。所有的整数都是正数，且不超过 $int$ 的范围。

### 输出格式

对于每个测试用例，输出一行，其中包含用例编号和战士可以随身携带的所有物品的最大总价值 。