给你四个整数 $$$n$$$、$$$B$$$、$$$x$$$ 和 $$$y$$$。您应该构建一个序列 $$$a_0, a_1, a_2, \dots, a_n$$$ 其中 $$$a_0 = 0$$$ 并且对于每个 $$$i \ge 1$$$ 您可以选择:
- $$$a_i = a_{i - 1} + x$$$
- 或 $$$a_i = a_{i - 1} - y$$$。
你的目标是构建这样一个序列$$$a$$$,使得$$$a_i \le B$$$ 对于所有$$$i$$$ 和$$$\sum\limits_{i=0}^{n}{a_i}$$$ 是最大可能的。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。接下来的 $$$t$$$ 案例如下。
每个测试用例的第一行也是唯一一行包含四个整数 $$$n$$$、$$$B$$$、$$$x$$$ 和 $$$y$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le B, x, y \le 10^9$$$)。
保证$$$n$$$的总和不超过$$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 可能的最大 $$$\sum\limits_{i=0}^{n}{a_i}$$$。
示例
输入 #1
3 5 100 1 30 7 1000000000 1000000000 1000000000 4 1 7 3
输出 #1
15 4000000000 -10
注意
在第一个测试用例中,最优序列 $$$a$$$ 是 $$$[0, 1, 2, 3, 4, 5]$$$。
在第二个测试用例中,最优序列 $$$a$$$ 为 $$$[0, 10^9, 0, 10^9, 0, 10^9, 0, 10^9]$$$。
在第三个测试用例中,最优序列 $$$a$$$ 是 $$$[0, -3, -6, 1, -2]$$$。