题目描述

给定四个整数 $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_i \le B$ 对所有 $i$ 成立的序列 $a$，并使 $\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}$。

说明/提示

在第一个测试用例中，最优的序列 $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]$。

由 ChatGPT 4.1 翻译

样例

3
5 100 1 30
7 1000000000 1000000000 1000000000
4 1 7 3

15
4000000000
-10