CF1733D2.Zero-One (Hard Version)

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 \lt 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.

本题为该问题的困难版本。在此版本中，满足 $n \le 5000$，且对 $x$ 和 $y$ 之间无任何限制。仅当两个版本的问题均被成功 hack 时，才允许进行 hack。

给定两个长度均为 $n$ 的二进制字符串 $a$ 和 $b$。你可以执行以下操作任意次（包括零次）：

• 选择两个下标 $l$ 和 $r$（满足 $l \lt r$）；
• 将 $a_l$ 变为 $(1 - a_l)$，并将 $a_r$ 变为 $(1 - a_r)$；
• 若 $l + 1 = r$，则该操作的代价为 $x$；否则，代价为 $y$。

你需要求出使 $a$ 等于 $b$ 所需的最小总代价；若无法实现，则输出说明不存在可行方案。

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

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。

每个测试用例由三行组成。每个测试用例的第一行包含三个整数 $n$、$x$ 和 $y$（$5 \le n \le 5000$，$1 \le x, y \le 10^9$）—— 字符串的长度以及每次操作的代价。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $a$，该字符串仅由数字 $0$ 和 $1$ 组成。

每个测试用例的第三行包含一个长度为 $n$ 的字符串 $b$，该字符串仅由数字 $0$ 和 $1$ 组成。

保证所有测试用例中 $n$ 的总和不超过 $5000$。

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

对于每个测试用例，若无法使 $a$ 等于 $b$，则输出 $-1$；否则，输出使 $a$ 等于 $b$ 所需的最小代价。

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.

在第一个测试用例中，选择下标 $2$ 和 $3$ 的代价为 $8$，这是最小代价。

在第二个测试用例中，我们可以执行以下操作：

• 选择下标 $1$ 和 $2$。代价为 $2$，此时 $a$ 变为 110001。
• 选择下标 $2$ 和 $3$。代价为 $2$，此时 $a$ 变为 101001。
• 选择下标 $3$ 和 $4$。代价为 $2$，此时 $a$ 变为 100101。
• 选择下标 $4$ 和 $5$。代价为 $2$，此时 $a$ 变为 100011。
• 选择下标 $5$ 和 $6$。代价为 $2$，此时 $a$ 变为 100000。

总代价为 $10$。

在第三个测试用例中，我们无法通过任意次数的操作使 $a$ 等于 $b$。

在第四个测试用例中，我们可以执行以下操作：

• 选择下标 $3$ 和 $6$。代价为 $3$，此时 $a$ 变为 0101011。
• 选择下标 $4$ 和 $6$。代价为 $3$，此时 $a$ 变为 0100001。

总代价为 $6$。

在第五个测试用例中，我们可以执行以下操作：

• 选择下标 $1$ 和 $6$。代价为 $4$，此时 $a$ 变为 110000。
• 选择下标 $2$ 和 $3$。代价为 $3$，此时 $a$ 变为 101000。

总代价为 $7$。

在第六个测试用例中，我们无需执行任何操作。