XY Sequence

题意翻译

给定四个整数 $n,B,x,y$。你将按照如下方式构造一个长度为 $n+1$ 的数列 $a_0,a_1,\cdots,a_n$： - 一开始，$a_0=0$。 - 你可以任意选择让 $a_i$ 的值为 $a_{i-1}+x$ 或 $a_{i-1}-y$。 请求出在使得 $\max\limits_{1\leqslant i\leqslant n} a_i\leqslant B$ 的前提下，$\sum\limits_{i=0}^n a_i$ 的最大值。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 10^4$。 - $1\leqslant n\leqslant 2\times 10^5$，$1\leqslant B,x,y\leqslant 10^9$。 Translated by Eason_AC

题目描述

You are given four integers $ n $ , $ B $ , $ x $ and $ y $ . You should build a sequence $ a_0, a_1, a_2, \dots, a_n $ where $ a_0 = 0 $ and for each $ i \ge 1 $ you can choose: - either $ a_i = a_{i - 1} + x $ - or $ a_i = a_{i - 1} - y $ . Your goal is to build such a sequence $ a $ that $ a_i \le B $ for all $ i $ and $ \sum\limits_{i=0}^{n}{a_i} $ is maximum possible.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Next $ t $ cases follow. The first and only line of each test case contains four integers $ n $ , $ B $ , $ x $ and $ y $ ( $ 1 \le n \le 2 \cdot 10^5 $ ; $ 1 \le B, x, y \le 10^9 $ ). It's guaranteed that the total sum of $ n $ doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print one integer — the maximum possible $ \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

说明

In the first test case, the optimal sequence $ a $ is $ [0, 1, 2, 3, 4, 5] $ . In the second test case, the optimal sequence $ a $ is $ [0, 10^9, 0, 10^9, 0, 10^9, 0, 10^9] $ . In the third test case, the optimal sequence $ a $ is $ [0, -3, -6, 1, -2] $ .