CF1733D1.Zero-One (Easy Version)

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.

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

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

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.