该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Tom 给了 33DAI 两个长度为 $n$ 的 $01$ 串 $a$ 与 $b$（下标从 $1$ 开始）。33DAI 可以操作 $a$ 任意多次（包括零次）：

每次操作选取两个下标 $l < r$（$1 \le l < r \le n$），同时翻转 $a_l$ 与 $a_r$。一次操作的代价只取决于两个下标是否相邻：若 $r = l + 1$，代价为 $x$；否则代价为 $y$。$x$ 与 $y$ 的大小关系没有限制。

求把 $a$ 变成 $b$ 所需的最小总代价。如果无法做到，输出 $-1$。

输入格式

从文件 bits.in 读入数据。

输入的第一行包含一个正整数 $t$，表示测试数据组数。

接下来依次给出 $t$ 组数据，每组数据的格式为：

第一行包含三个整数 $n, x, y$，分别表示串长与两种操作的代价。

第二行包含一个长度为 $n$ 的仅由 0、1 组成的字符串 $a$。

第三行包含一个长度为 $n$ 的仅由 0、1 组成的字符串 $b$。

输出格式

输出到文件 bits.out。

对于每组数据，输出一行一个整数：把 $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

8
10
-1
6
7
0

样例 1 解释

第一组数据：$a$ 与 $b$ 只有第 $2, 3$ 位不同。对下标对 $(2, 3)$ 做一次相邻操作， $a$ 就变成了 $b$，代价为 $x = 8$。

第二组数据：$a$ 与 $b$ 在第 $1, 6$ 位不同。依次对下标对 $(1,2)$、$(2,3)$、$(3,4)$、$(4,5)$、$(5,6)$ 各做一次相邻操作（第 $2,3,4,5$ 位各被翻转两次、不受影响），$a$ 就变成了 $b$，总代价为 $5x = 10$。

第三组数据：答案是 $-1$，即不存在把 $a$ 变成 $b$ 的操作方案。

第四组数据：$a$ 与 $b$ 在第 $3, 4$ 位不同，这里 $x = 8,\ y = 3$。 对下标对 $(3, 6)$ 与 $(4, 6)$ 各做一次不相邻操作（两次都满足 $r > l + 1$）： 第 $3, 4$ 位各被翻转一次，第 $6$ 位被翻转两次而抵消，$a$ 就变成了 $b$，总代价为 $2y = 6$。

第五组数据：$a$ 与 $b$ 在第 $1, 2, 3, 6$ 位不同，这里 $x = 3,\ y = 4$。 对下标对 $(1, 2)$ 做一次相邻操作（代价 $x = 3$），再对下标对 $(3, 6)$ 做一次不相邻操作 （代价 $y = 4$），$a$ 就变成了 $b$，总代价为 $7$。

第六组数据：两个串已经完全相同，不需要做任何操作。

样例 2

见 bits2.in 与 bits2.ans。

样例 3

见 bits3.in 与 bits3.ans。

数据范围

对于所有测试数据，保证：

• $1 \le t \le 1000$；
• $5 \le n \le 5000$；
• $1 \le x, y \le 10^9$；
• $a$ 与 $b$ 均只由字符 0、1 组成，长度均为 $n$；
• 单个测试文件中所有测试用例的 $n$ 之和不超过 $5000$。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。