Charlie 极度渴望提高他的编程技能。

从清爽状态开始，他可以努力工作，在连续的 $x$ 天内每天获得 $a$ 点技能点，之后他会进入疲惫状态。只要他保持疲惫状态继续工作，每天可以获得 $b$ 点技能点。或者，他可以在任何时候选择连续休息 $y$ 天，之后他可以重新恢复到清爽状态。

在大赛开始前只有 $n$ 天时间，且 Charlie 在第 1 天处于清爽状态。请帮助他计算出能够获得的最大技能点数。

输入格式

输入的第一行包含测试用例的数量 $t$ ($1 \le t \le 10,000$)。

每个测试用例包含五个整数 $n, a, b, x, y$：

• $n$ ($1 \le n \le 10^9$)：可用的天数。
• $a, b$ ($10^9 \ge a \ge b \ge 1$)：分别表示清爽状态和疲惫状态下每天获得的技能点数。
• $x, y$ ($1 \le x, y \le 10^9$)：分别表示高技能获取天数（清爽状态持续天数）和休息天数。

输出格式

对于每个测试用例，输出一个整数，表示可以获得的最大技能点数。

样例

输入样例 1

6
2 2 2 2 2
4 4 2 3 3
5 3 2 3 1
5 4 1 3 1
99 80 40 30 5
10 6 1 6 1

输出样例 1

4
14
13
16
7120
54

输入样例 2

3
1 1 1 1 1
100000000 100000000 100000000 100000000 100000000
91965976 48437754 31825605 1671338 8268468

输出样例 2

1
10000000000000000
2954637341500842