零一串（困难版）

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

给定两个长度为 $n$ 的二进制字符串 $a$ 和 $b$。你可以进行若干次操作（也可以不操作）。每次选择两个下标 $l<r$，并同时翻转 $a_l$ 与 $a_r$：

• 若 $l+1=r$，本次操作的代价为 $x$；
• 否则，本次操作的代价为 $y$。

求使 $a$ 变为 $b$ 的最小总代价；若无法做到，输出 $-1$。

输入格式

第一行一个整数 $t$，表示测试组数。

每组测试：

• 第一行三个整数 $n,x,y$；
• 第二行一个长度为 $n$ 的二进制字符串 $a$；
• 第三行一个长度为 $n$ 的二进制字符串 $b$。

输出格式

对每组测试输出一行一个整数，表示最小总代价；无解时输出 $-1$。

样例输入 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

数据范围

对所有数据，$1\le t\le1000$，$5\le n\le5000$，$1\le x,y\le10^9$，所有测试组的 $n$ 之和不超过 $5000$。字符串仅含 0 和 1。