← 返回题目列表

Codeforces · 1978/B

B. 新面包店

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

鲍勃决定开一家面包店。开业当天,他烤了 $$$n$$$ 的面包可以卖。一个包子的通常价格是$$$a$$$硬币,但为了吸引顾客,鲍勃组织了以下促销活动:

- Bob 选择某个整数 $$$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$$$ 面包可以获得的最大利润。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的唯一行包含三个整数 $$$n$$$、$$$a$$$ 和 $$$b$$$ ($$$1 \le n, a, b \le 10^9$$$) — 包子的数量、包子的通常价格以及以修改后的价格出售的第一个包子的价格。

输出

对于每个测试用例,输出一个整数——Bob 可以获得的最大利润。

示例

输入 #1

7
4 4 5
5 5 9
10 10 5
5 5 11
1000000000 1000000000 1000000000
1000000000 1000000000 1
1000 1 1000

输出 #1

17
35
100
45
1000000000000000000
1000000000000000000
500500

注意

在第一个测试用例中,Bob 最好选择 $$$k = 1$$$。然后他会以 $$$5$$$ 硬币的价格出售一个面包,并以正常价格出售三个面包,每个面包为 $$$4$$$ 硬币。那么利润将为$$$5 + 4 + 4 + 4 = 17$$$ 硬币。

在第二个测试用例中,Bob 最好选择 $$$k = 5$$$。然后他会按照修改后的价格出售所有的包子,获得$$$9 + 8 + 7 + 6 + 5 = 35$$$ 币的利润。

在第三个测试用例中,Bob 最好选择 $$$k = 0$$$。然后他会以平常的价格出售所有的包子,获得$$$10\cdot 10 = 100$$$币的利润。