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

题目描述

33DAI 要把 01 串 $a$ 变成 01 串 $b$。

给定两个长度均为 $n$ 的 01 串 $a$ 与 $b$，下标从 $1$ 开始。

一次操作是：选择两个下标 $l < r$（$1 \le l < r \le n$），把 $a_l$ 与 $a_r$ 同时取反 （$0$ 变成 $1$，$1$ 变成 $0$）。

每次操作的代价只取决于两个下标是否相邻：

• 若 $r = l + 1$，代价为 $x$；
• 否则（$r > l + 1$），代价为 $y$。

操作可以进行任意多次，顺序不限。请你求出把 $a$ 变成 $b$ 所需的最小总代价； 如果无论如何都无法把 $a$ 变成 $b$，输出 $-1$。

输入格式

从文件 binary.in 读入数据。

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

接下来依次给出 $t$ 组数据，每组数据占三行：

• 第一行包含三个整数 $n$、$x$、$y$，分别表示串的长度与两种操作的代价；
• 第二行包含一个长度为 $n$ 的 01 串 $a$；
• 第三行包含一个长度为 $n$ 的 01 串 $b$。

输出格式

输出到文件 binary.out。

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

4
5 8 7
01001
00101
5 7 2
01000
11011
7 8 3
0111001
0100001
5 10 1
01100
01100

8
-1
6
0

样例 1 解释

第一组数据中 $a$ 与 $b$ 只有第 $2$、$3$ 位不同，选取下标 $2$ 与 $3$ 做一次相邻操作， $a$ 就变成了 00101，与 $b$ 相同，代价为 $x = 8$。

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

第三组数据可以这样操作：先选下标 $3$ 与 $6$（代价 $y = 3$），此时 $a$ 变成 0101011； 再选下标 $4$ 与 $6$（代价 $y = 3$），此时 $a$ 变成 0100001，与 $b$ 相同。总代价为 $6$。

第四组数据中 $a$ 已经等于 $b$，不需要任何操作，代价为 $0$。

样例 2

见 binary2.in 与 binary2.ans。

样例 3

见 binary3.in 与 binary3.ans。

数据范围

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

• $1 \le t \le 600$；
• $5 \le n \le 3000$；
• $1 \le y \le x \le 10^9$；
• 单个测试文件中所有测试用例的 $n$ 之和不超过 $3000$。

子任务

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

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