B. 新面包店

每次测试时间限制：$1$ 秒 每次测试内存限制：$256$ 兆字节

鲍勃决定开一家面包店。开业当天，他烤了$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$个面包能获得的最大利润。

输入

每组测试包含多个测试用例。 第一行输入一个整数$t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例仅占一行，包含三个整数$n$、$a$、$b$（$1 \le n,a,b \le 10^9$），分别代表面包的数量、面包的正常售价、促销活动中第一个面包的售价。

输出

对于每个测试用例，输出一个整数，表示鲍勃能获得的最大利润。

样例输入

$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$

核心解题逻辑（基于标程）

一、关键分类讨论

我们根据促销起始价 $\boldsymbol{b}$ 和正常售价 $\boldsymbol{a}$ 的大小关系，分两种核心情况计算最大利润：

1. 当 $\boldsymbol{b < a}$ 时 所有促销面包的价格都会低于正常售价 $\boldsymbol{a}$，此时选择 $\boldsymbol{k=0}$ 利润最大，即全部面包按原价销售。 总利润公式：$\boldsymbol{a \cdot n}$

2. 当 $\boldsymbol{b \ge a}$ 时 最优的促销数量为 $\boldsymbol{k = \min(b-a, n)}$，这个取值是利润最大化的关键：

• 若 $k$ 大于该值，部分面包的促销价会低于 $a$，利润减少；
• 若 $k$ 小于该值，本可以高价卖出的面包按原价出售，利润未达最大。

二、利润计算原理

促销的 $\boldsymbol{k}$ 个面包价格构成等差数列： 首项为 $\boldsymbol{b}$，末项为 $\boldsymbol{b-k+1}$，总数量为 $\boldsymbol{k}$。 根据等差数列求和公式，促销部分总利润为： $\boldsymbol{\frac{b + (b-k+1)}{2} \cdot k}$

剩余的 $\boldsymbol{n-k}$ 个面包按正常售价销售，这部分利润为： $\boldsymbol{(n-k) \cdot a}$

三、最终最大利润公式

将两部分利润相加，得到总最大利润： $\boldsymbol{ans = \frac{b + (b-k+1)}{2} \cdot k + (n-k) \cdot a}$ 其中固定取值 $\boldsymbol{k = \min(b-a, n)}$。