write a go solution for Description:
This is the hard version of this problem. In this version, n<=5000 holds, and this version has no restriction between x and y. You can make hacks only if both versions of the problem are solved.

You are given two binary strings a and b, both of length n. You can do the following operation any number of times (possibly zero).

- Select two indices l and r (l<r).
- Change a_l to (1-a_l), and a_r to (1-a_r).
- If l+1=r, the cost of the operation is x. Otherwise, the cost is y.

You have to find the minimum cost needed to make a equal to b or say there is no way to do so.

Input Format:
The first line contains one integer t (1<=t<=1000) — the number of test cases.

Each test case consists of three lines. The first line of each test case contains three integers n, x, and y (5<=n<=5000, 1<=x,y<=10^9) — the length of the strings, and the costs per operation.

The second line of each test case contains the string a of length n. The string only consists of digits 0 and 1.

The third line of each test case contains the string b of length n. The string only consists of digits 0 and 1.

It is guaranteed that the sum of n over all test cases doesn't exceed 5000.

Output Format:
For each test case, if there is no way to make a equal to b, print -1. Otherwise, print the minimum cost needed to make a equal to b.

Note:
In the first test case, selecting indices 2 and 3 costs 8, which is the minimum.

In the second test case, we can perform the following operations.

- Select indices 1 and 2. It costs 2, and a is 110001 now.
- Select indices 2 and 3. It costs 2, and a is 101001 now.
- Select indices 3 and 4. It costs 2, and a is 100101 now.
- Select indices 4 and 5. It costs 2, and a is 100011 now.
- Select indices 5 and 6. It costs 2, and a is 100000 now.

The total cost is 10.

In the third test case, we cannot make a equal to b using any number of operations.

In the fourth test case, we can perform the following operations.

- Select indices 3 and 6. It costs 3, and a is 0101011 now.
- Select indices 4 and 6. It costs 3, and a is 0100001 now.

The total cost is 6.

In the fifth test case, we can perform the following operations.

- Select indices 1 and 6. It costs 4, and a is 110000 now.
- Select indices 2 and 3. It costs 3, and a is 101000 now.

The total cost is 7.

In the sixth test case, we don't have to perform any operation.. Output only the code with no comments, explanation, or additional text.