B. XY последовательность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам заданы четыре целых числа $$$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}$$$.

Пример
Входные данные
3
5 100 1 30
7 1000000000 1000000000 1000000000
4 1 7 3
Выходные данные
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]$$$.