P7777 JROI-2 Shelter

And it's a long way forward So trust in me I'll give them shelter like you've done for me And I know, I'm not alone You'll be watching over us Until ... A little girl lies diagonally on a cockpit chair, her long hair flowing from her shoulders to the floor. A smile blooms at the corner of her mouth, and the display beside her reads "Return to the Third Planet". The teddy bear in her arms has her name written on it, Rin. — [Shelter](https://www.bilibili.com/video/BV1ys41147Gv) ---

When Rin and her father were still on Earth, they often played a stone game. Dad set up $n$ piles of stones, numbered from $1$ to $n$. The rules are as follows. Each time, Rin can take stones in one of two ways: - Choose a number $i$, take away the $i$-th pile of stones, with a cost of $i \times p$. - Choose two numbers $i,j$, take away the $i$-th and $j$-th piles of stones, with a cost of $|i-j| \times q$. Here, $p,q$ are constants set in advance by Dad. Rin wants to know the minimum total cost to take away all the stones. There are only 1919810114514 seconds left before the disaster strikes the Third Planet. Dad still needs 1919810114513.7 seconds to place Rin into the cockpit and start the machine to let Rin enter "Shelter". Therefore, you only have 0.3 seconds to help Rin compute the result!

**This problem has multiple test cases.** The first line contains an integer $T$ representing the number of test cases. The next $T$ lines each contain three integers $n,p,q$, representing the number of stone piles and the two constants.

Output $T$ lines, each containing one integer representing the answer.

#### Explanation for Sample 1 First test case: 1. Use the first operation to take away pile $1$, with cost $1 \times 2=2$. 2. Use the second operation to take away piles $2,3$, with cost $|2-3| \times 3=3$. 3. Use the second operation to take away piles $4,5$, with cost $|4-5| \times 3=3$. The minimum cost is $2+3+3=8$. Second test case: 1. Use the first operation to take away pile $1$, with cost $1 \times 1=1$. 2. Use the first operation to take away pile $2$, with cost $2 \times 1=2$. 3. Use the second operation to take away piles $3,4$, with cost $|3-4| \times 5=5$. The minimum cost is $1+2+5=8$. #### Constraints and Notes **This problem uses bundled tests.** - Subtask 1 (1 pts): $p,q =0$. - Subtask 2 (1 pts): $n=1$. - Subtask 3 (30 pts): $T \le 5 \times 10^4$, $n \le 5 \times 10^5$. - Subtask 4 (33 pts): $T \le 10^6$, $n \le 5 \times 10^5$. - Subtask 5 (35 pts): no special restrictions. For $100\%$ of the testdata, $1 \le n \le 10^9$, $0 \le p,q \le 100$, $1 \le T \le 10^6$. The Extra Example in the attachment satisfies $T=10^4$ and can be used for debugging. ----- Source: [JROI-2 Summer Fun Round](https://www.luogu.com.cn/contest/30241) - T1 Idea & Solution: [一只书虫仔](/user/114914) Standard Solution & Data: [Tony2](/user/171288) Retest: [Cocoly1990](/user/183026) Translated by ChatGPT 5