Боб решил открыть булочную. В день открытия он испёк \(n\) булок, которые может продать. Обычная цена булки равна \(a\) монет, но чтобы привлечь покупателей, Боб организовал следующую акцию:
- Боб выбирает некоторое целое число \(k\) (\(0 \le k \le \min(n, b)\)).
- Первые \(k\) булок Боб продаёт по изменённой цене. В таком случае цена \(i\)-й (\(1 \le i \le k\)) проданной булки равна \((b - i + 1)\) монет.
- Оставшиеся \((n - k)\) булок Боб продаёт по \(a\) монет за каждую.
Обратите внимание, что \(k\) может равняться \(0\). В таком случае Боб продаст все булки по \(a\) монет за каждую.
Помогите Бобу определить максимальную прибыль, которую он может получить, если продаст все \(n\) булок.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальную прибыль, которую может получить Боб.
Примечание
В первом наборе входных данных Бобу выгодно выбрать \(k = 1\). Тогда он продаст одну булку за \(5\) монет, и три булки по обычной цене за \(4\) монеты. Тогда прибыль равна \(5 + 4 + 4 + 4 = 17\) монет.
Во втором наборе входных данных Бобу выгодно выбрать \(k = 5\). Тогда он продаст все булки по изменённой цене и получит прибыль \(9 + 8 + 7 + 6 + 5 = 35\) монет.
В третьем наборе входных данных Бобу выгодно выбрать \(k = 0\). Тогда он продаст все булки по обычной цене и получит прибыль \(10 \cdot 10 = 100\) монет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
4 4 5
5 5 9
10 10 5
5 5 11
1000000000 1000000000 1000000000
1000000000 1000000000 1
1000 1 1000
|
17
35
100
45
1000000000000000000
1000000000000000000
500500
|