题目描述

在遥远的未来，人类已经跨入了星际时代，与多个外星文明建立了联系。为了高效地进行跨星际通讯，科学家们发明了一种基于二进制编码的通讯协议。然而，由于宇宙中的干扰和传输错误，接收到的二进制信息有时会出现偏差。为了保证信息的准确性，你需要设计一个程序，通过最少的校正操作，将接收到的二进制编码调整为原始发送的编码。你是星际通讯中心的一名技术人员，负责监测和校正从外星文明接收到的二进制信息。每个二进制信息都是一个长度为 n 的字符串，只包含数字 0 和 1。由于传输过程中的干扰，接收到的信息可能与原始发送的信息不一致。

为了校正这些错误，你可以使用一种特殊的操作：选择字符串中的两个位置 l 和 r（l<r），并将这两个位置上的二进制数字进行翻转（即 0 变为 1，1 变为 0）。这种操作有两种代价：

（1）如果 l+1=r，即相邻的两个位置，校正代价为 x。

（2）否则，校正代价为 y。

你的任务是编写一个程序，计算将接收到的二进制信息校正为原始发送信息所需的最小代价。如果无法完全校正，则输出 −1。

输入格式

输入的第一行包含一个整数 t（1≤t≤1000），表示测试用例的数量。

每个测试用例包含三行：

第一行包含三个整数 n，x 和 y（5≤n≤5000，1≤x,y≤1e9），分别表示二进制信息的长度、相邻位置校正的代价和非相邻位置校正的代价。

第二行包含一个长度为 n 的二进制字符串 a，表示接收到的信息。

第三行包含一个长度为 n 的二进制字符串 b，表示原始发送的信息。

输出格式

对于每个测试用例，如果无法将接收到的信息校正为原始发送的信息，则输出 −1。否则，输出校正所需的最小代价。

20%的数据保证：5<=n<=10, 1<=t<=10,1<=x,y<=100

20%的数据保证：5<=n<=500，1<=t<=10,1<=x,y<=10000，并且x>y

20%的数据保证：5<=n<=500，1<=t<=10,1<=x,y<=10000，并且x<=y

20%的数据保证：5<=n<=500，1<=t<=10,1<=x,y<=1e9

20%的数据保证：5<=n<=5000，1<=t<=1000,1<=x,y<=1e9

输入/输出例子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