Zero-One (Easy Version)
Contest: Codeforces Round 821 (Div. 2)
Difficulty rating: 1400
Tags: constructive algorithms, greedy, math

This is the easy version of the problem. In this version, $$$n \le 3000$$$, $$$x \ge y$$$ holds. 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 600$$$) — 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 3000$$$, $$$1 \le y \le x \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 $$$3000$$$.

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 possible cost.

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

In the third 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 fourth test case, we don't have to perform any operations.

Example input:
4
5 8 7
01001
00101
5 7 2
01000
11011
7 8 3
0111001
0100001
5 10 1
01100
01100

Example output:
8
-1
6
0

Editorial:
Consider another binary string $$$c$$$, in which $$$c_i = a_i \oplus b_i$$$ ($$$1 \le i \le n$$$). So doing an operation means selecting two indices of $$$c$$$ and flipping them. Also, let's define $$$d$$$ is the number of $$$1$$$ in $$$c$$$. Because the parity of $$$d$$$ never changes, the answer is $$$-1$$$ if $$$d$$$ is odd.
If $$$d$$$ is even, classify the cases:
$$$[1]$$$ If $$$d = 2$$$ and two $$$1$$$s are adjacent, the answer is $$$\min(x, 2y)$$$. Because $$$n \ge 5$$$ holds, we can always replace one $$$x$$$-cost operation with two $$$y$$$-cost operations.
$$$[2]$$$ If $$$d = 2$$$ and two $$$1$$$s are not adjacent, the answer is $$$y$$$.
$$$[3]$$$ If $$$d \ne 2$$$, select $$$i$$$-th $$$1$$$ and $$$(i+\frac{d}{2})$$$-th $$$1$$$ each ($$$1 \le i \le \frac{d}{2}$$$). This costs $$$\frac{d}{2} \times y$$$, and we showed the cost cannot be reduced more in hint 3.