有一个包含 $$$n$$$ 行和 $$$10^6 + 2$$$ 列的图表,其中行编号从 $$$1$$$ 到 $$$n$$$,列编号从 $$$0$$$ 到 $$$10^6 + 1$$$:
让我们用 $$$(i, j)$$$ 表示 $$$i$$$ 行和 $$$j$$$ 列中的节点。
最初,对于每个 $$$i$$$,第 $$$i$$$ 行只有一个障碍物 - 在节点 $$$(i, a_i)$$$ 处。您想要移动一些障碍物,以便通过移动该图的边(无法穿过障碍物)从节点 $$$(1, 0)$$$ 到达节点 $$$(n, 10^6+1)$$$。将一个障碍物移动到相邻的无边节点需要花费 $$$u$$$ 或 $$$v$$$ 硬币,如下所示:
- 如果节点$$$(i, j)$$$中有障碍物,您可以使用$$$u$$$硬币将其移动到$$$(i-1, j)$$$或$$$(i+1, j)$$$,如果该节点存在并且当前该节点没有障碍物。
- 如果节点$$$(i, j)$$$中有障碍物,您可以使用$$$v$$$硬币将其移动到$$$(i, j-1)$$$或$$$(i, j+1)$$$,如果该节点存在且当前该节点没有障碍物。
- 请注意,您无法将障碍物移动到网格之外。例如,您无法将障碍物从 $$$(1,1)$$$ 移动到 $$$(0,1)$$$。
请参阅上图以更好地理解。
现在您需要计算从节点 $$$(1, 0)$$$ 穿过该图的边缘而不穿过障碍物到达节点 $$$(n, 10^6+1)$$$ 所需花费的最少硬币数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$u$$$ 和 $$$v$$$ ($$$2 \le n \le 100$$$, $$$1 \le u, v \le 10^9$$$)——图中的行数以及分别垂直和水平移动所需的硬币数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — 其中 $$$a_i$$$ 表示第 $$$i$$$ 行中的障碍物位于节点 $$$(i, a_i)$$$ 中。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^4$$$。
输出
对于每个测试用例,输出一个整数 - 从节点 $$$(1, 0)$$$ 穿过该图的边缘而不穿过障碍物到达节点 $$$(n, 10^6+1)$$$ 所需花费的最少硬币数量。
可以证明,在问题的约束下,总有一种方法可以使这样的旅行成为可能。
示例
输入 #1
3 2 3 4 2 2 2 3 4 3 2 2 4 3 3 2
输出 #1
7 3 3
注意
在第一个示例中,两个障碍物位于 $$$(1, 2)$$$ 和 $$$(2,2)$$$ 处。您可以将 $$$(2, 2)$$$ 上的障碍物移动到 $$$(2, 3)$$$,然后移动到 $$$(1, 3)$$$。总成本为 $$$u+v = 7$$$ 硬币。
在第二个示例中,两个障碍物位于 $$$(1, 3)$$$ 和 $$$(2,2)$$$ 处。您可以将$$$(1, 3)$$$上的障碍物移至$$$(2, 3)$$$。成本为 $$$u = 3$$$ 硬币。