题目描述

小美有一个长度为 $n$ 的数组 $a_{1}, a_{2}, \ldots, a_{n}$ , 他可以对数组进行如下操作：

• 删除第一个元素 $a_{1}$ , 同时数组的长度减 $1$，花费为 $x$ 。
• 删除整个数组，花费为 $k \times \operatorname{MEX}(a)$ （其中 $\operatorname{MEX}(a)$ 表示 $a$ 中未出现过的最小非负整数。例如 $[0,1,2,4]$ 的 $\operatorname{MEX}$ 为 $3$ ）。

小美想知道将 $a$ 数组全部清空的最小代价是多少, 请你帮帮他吧.

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$（$1 \leq T \leq 1000$） 代表数据组数, 每组测试数据描述如下:

第一行输入三个正整数 $n, k, x$ （$1 \leq n \leq 2 \times 10^{5}$$,$$1 \leq k, x \leq 10^{9}$） 代表数组中的元素数量、删除整个数组的花费系数、删除单个元素的花费。

a除此之外, 保证所有的 $n$ 之和不超过 $2 \times 10^{5}$ 。

输出描述

对于每一组测试数据, 在一行上输出一个整数表示将数组中所有元素全部删除的最小花费。

样例输入输出

1
6 3 3
4 5 2 3 1 0

15

说明

若不执行操作一就全部删除, $\operatorname{MEX}\{4,5,2,3,1,0\}=6$ ，花费 $18$ ； 若执行一次操作一后全部删除, $\operatorname{MEX}\{5,2,3,1,0\}=4$ ，花费 $3+12$ ； 若执行两次操作一后全部删除, $\operatorname{MEX}\{2,3,1,0\}=4$,花费 $6+12$ ； 若执行三次操作一后全部删除, $\operatorname{MEX}\{3,1,0\}=2$ , 花费 $9+6$ ； 若执行四次操作一后全部删除, $\operatorname{MEX}\{1,0\}=2$ , 花费 $12+6$ 若执行五次操作一后全部删除, $\operatorname{MEX}\{0\}=1$ , 花费 $15+3$ ； 若执行六次操作一, $\operatorname{MEX}\{\}=0$ , 花费 $18$ ;