当前没有测试数据。

小田的连通图

题目描述

小田得到了 $n$ 个结点，第 $i$ 个结点的权值为 $A_i$ 。

初始时，每个结点都为孤立的点，互不连通。

现在小田需要往里面加若干条无向边，使得所有点构成一张无向连通图。

我们定义在两个节点之间加边的代价为：如果两个点的权值都是偶数或者都是奇数，代价为 $a$，否则为 $b$ 。

现在，你需要帮小田算出所有点构成一张无向连通图的最小代价之和。

注：加边的过程中不能出现重边和自环。

连通图：如果这个图中任意两点都有路径可以到达，那么这个图就是连通图，例如：一个图有三个点 $A,B,C$，假设 $A,B$、$B,C$ 之间各有一条无向边，那么它就是连通图。

输入描述

第一行一个正整数 $t$，表示输入的数据组数。

对于每组数据的格式为：

第一行三个整数 $n, a, b$，代表点的数量、连通结点的两种代价。

第二行输入 $n$ 个整数 $A_i$，表示第 $i$ 个结点的权值。

输出描述

输出共 $T$ 行，每行一个整数，表示所有点构成一张无向连通图的最小代价之和。

输入输出样例

输入 #1

2
5 1 2
0 1 2 3 4
5 100 0
1 2 3 4 5

输出 #1

5
0

输入 #2

1
4 -1 -2
1 1 1 2 2

输出 #2

-9

说明/提示

【样例 1 解释】

对于第一组数据，显然先奇数与奇数相连、偶数与偶数相连，最后再连一组奇数与偶数结点即可，总代价为 $5$ 。

对于第二组数据，连奇偶结点，权值为 $0$，总代价为 $0$。

【样例 2 解释】

对于第一组数据，因为两个代价都是负数，所以就是把所有能连的边都连上，总代价为 $-9$ 。

【数据范围】

对于 $10 \%$ 的数据，有 $a \le 0, b \le 0$。

对于另外 $30 \%$ 的数据，有：$a>0,b>0$ 。

对于所有测试数据，有：$1 \le n \le 2 \times 10^{5}, -100 \le a,b \le 100, 0 \le A_{i} \le 10^{6}$ 。

保证对于单个测试用例，所有测试数据 $\sum\limits n \le 2 \times 10^{5}$ 。