Вам заданы четыре целых числа \(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}\) максимально возможна.
Выходные данные
Для каждого набора выведите одно число — максимально возможное значение \(\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]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 100 1 30
7 1000000000 1000000000 1000000000
4 1 7 3
|
15
4000000000
-10
|