### 问题描述 蓝桥小学又开始施工啦~ 这次他们打算重建所有的宿舍楼，因此需要先把宿舍楼全部摧毁。 已知蓝桥小学有 $n$ 栋排成一排的宿舍，编号为 $1$ 到 $n$，第 $i$ 栋宿舍的高度为 $h_i$，共有两种摧毁宿舍的方法:**（注：摧毁后的宿舍高度为 $0$）** $1.$ 花费 $X$ 元摧毁任意一栋宿舍。 $2.$ 选择一段区间 $[l,r]$（$l0,h_r>0$），如果满足 $(l , r ]$ 区间内只有 $r$ 宿舍的高度大于等于 $l$ 宿舍的高度，则可以花费 $Y$ 元摧毁 $[l, r]$ 区间的所有宿舍（$[l,r]$ 中可以包含已被摧毁的宿舍）。 现在给出所有宿舍楼的高度和 $X,Y$，你能算出摧毁所有宿舍楼的最小预算吗？ ### 输入格式 输入第 $1$ 行包含一个正整数 $T$，表示有 $T$ 组测试数据。 每组测试数据的第 $1$ 行包含三个整数 $n,X,Y$，分别表示宿舍数和两种摧毁方法的花费。 每组测试数据的第 $2$ 行包含 $n$ 个整数，其中第 $i$ 个整数 $h_i$ 表示编号为 $i$ 的宿舍的高度。 **题目保证 $T$ 组测试数据的宿舍数 $n$ 之和不大于 $500$！** ### 输出格式 对于每组测试数据，输出一行，这一行包含一个整数，表示摧毁所有宿舍楼的最小花费。 ### 样例输入 ``` 3 5 5 7 2 1 3 1 5 5 10 10 10 8 5 10 1 1 1 5 10 ``` ### 样例输出 ``` 12 20 1 ``` ### 说明/提示 对于所有测试数据，$1\leq T\leq 20，1\leq n\leq 500，1\leq X,Y\leq 10^5，1\leq h_i\leq 10^9$。 样例中，先花费 $5$ 元摧毁 $3$ 号宿舍，宿舍楼的高度变为 $2\ 1 \ 0\ 1\ 5$，再花费 $7$ 元摧毁 $[1,5]$ 区间。