← 返回题目列表

Codeforces · 1657/B

B. XY 序列

中文机器翻译题面 查看原题

给你四个整数 $$$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]$$$。