You are given an array A which consists of N elements. Each element of array is either zero or one. Your task is to convert the given array into a good array with a minimum cost.
Good array: In a good array, select any subarray of even length M and the sum of elements in the subarray will be M/2.
In order to transform an array to good array, you can perform the following two operations as many times as you want:
- Choose any index 1≤i≤N and if it is currently 0, then convert it to 1 for X coins.
- Choose any index 1≤i≤N and if it is currently 1, then convert it to 0 for Y coins.
Your task is to minimize the cost of transformation of an array to good array.
Input format
- The first line contains T denoting the number of test cases.
- The first line of each test case contains three space-separated integers N, X, and Y.
- The second line of each test case consists of N space-separated integers of array A.
Output format
For each test case, print one line denoting the minimum cost to transform array A into a good array.
Constraints
1≤T≤100
1≤N≤104
0≤Ai≤1
1≤X,Y≤109
First test case: Array is [1,1], there is only one subarray which is of even length (2), i.e. complete subarray [1,1], it is not good array because for a subarray of size M i.e 2 in our case, sum must be M/2 i.e 1. But sum is 2 for this subarray, so this does not follow property of good subarray.
So here we need convert array to either [1,0] or [0,1], cost is 1 in either case.
Second test case: Array is [0,1], there is only one subarray which is of even length (2), i.e. complete subarray [0,1], it is good array because for a subarray of size M i.e 2 in our case, sum must be M/2 i.e 1. Here sum is 2 for this subarray, so this does follow property of good subarray.
So we don't need to perform any operation.
