Description: This is the hard version of this problem. In this version, $$$n \le 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 \le t \le 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 \le n \le 5000$$$, $$$1 \le x, y \le 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.