Zero-One (Hard Version)
Contest: Codeforces Round 821 (Div. 2)
Difficulty rating: 2000
Tags: dp, greedy

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$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

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.

Example input:
6
5 8 9
01001
00101
6 2 11
000001
100000
5 7 2
01000
11011
7 8 3
0111001
0100001
6 3 4
010001
101000
5 10 1
01100
01100

Example output:
8
10
-1
6
7
0

Editorial:
(Continued from D1 editorial)
If $$$x < y$$$, greedy approach doesn't work. Let's use DP. Define $$$z0[i][j]$$$ as the minimal cost when there is $$$j$$$ $$$1$$$s in first $$$i$$$ elements of $$$c$$$ and $$$c_i = 0$$$, and $$$z1[i][j]$$$ as the minimal cost when there is $$$j$$$ $$$1$$$s in first $$$i$$$ elements of $$$c$$$ and $$$c_i = 1$$$. Initially all table values are $$$\infty$$$.
First, check $$$c_1$$$. If $$$c_1 = 0$$$, set $$$z0[1][0]$$$ to $$$0$$$. Otherwise, set $$$z1[1][1]$$$ to $$$0$$$.
Then, check the following elements from $$$c_2$$$ to $$$c_n$$$ in turn.
$$$[4]$$$ If $$$c_i = 0$$$,
• $$$z0[i][j] = \min(z0[i - 1][j], z1[i - 1][j]),$$$
• $$$z1[i][j] = \begin{cases} \min(z0[i - 1][j] + y, z1[i - 1][j] + x), & \text{if } j \le 1 \\ \min(z0[i - 1][j] + y, z1[i - 1][j] + x, z0[i - 1][j - 2] + x, z1[i - 1][j - 2] + y), & \text{if } j > 1,\end{cases}$$$
$$$[5]$$$ If $$$c_i = 1$$$,
• $$$z0[i][j] = \begin{cases} \min(z0[i - 1][j + 1] + y, z1[i - 1][j + 1] + x), & \text{if } j = 0 \\ \min(z0[i - 1][j + 1] + y, z1[i - 1][j + 1] + x, z0[i - 1][j - 1] + x, z1[i - 1][j - 1] + y), & \text{if } 0 < j \le i \\ min(z0[i][j], z0[i - 1][j - 1] + x, z1[i - 1][j - 1] + y), & \text{if } j = i + 1,\end{cases}$$$
• $$$z1[i][j] = \begin{cases} \infty, & \text{if } j = 0 \\ min(z0[i - 1][j - 1], z1[i - 1][j - 1]), & \text{if } j > 0,\end{cases}$$$
for $$$0 \le j \le i + 1$$$. The answer is $$$z[n][0]$$$.