这是这个问题的困难版本。在这个版本中,$$$n \le 5000$$$成立,并且这个版本在$$$x$$$和$$$y$$$之间没有限制。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
给定两个二进制字符串 $$$a$$$ 和 $$$b$$$,长度均为 $$$n$$$。您可以执行以下操作任意次数(可能为零)。
- 选择两个索引 $$$l$$$ 和 $$$r$$$ ($$$l < r$$$)。
- 将 $$$a_l$$$ 更改为 $$$(1 - a_l)$$$,将 $$$a_r$$$ 更改为 $$$(1 - a_r)$$$。
- 如果 $$$l + 1 = r$$$,则操作成本为 $$$x$$$。否则,成本为$$$y$$$。
你必须找到使 $$$a$$$ 等于 $$$b$$$ 所需的最低成本,或者说没有办法这样做。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,如果无法使 $$$a$$$ 等于 $$$b$$$,则打印 $$$-1$$$。否则,打印使 $$$a$$$ 等于 $$$b$$$ 所需的最小成本。
示例
输入 #1
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
输出 #1
8 10 -1 6 7 0
注意
在第一个测试用例中,选择索引 $$$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$$$。
在第六个测试用例中,我们不必执行任何操作。