Zero-One (Easy Version)

题意翻译

两个长度为 $n$ 的二进制字符串 $a$ 和 $b$。你可以进行如下操作若干次（可以为0次）： - 选两个数 $l$ 和 $r\ $ $(\ l\ <\ r\ )$，对 $a_l$、$a_r$ 取反 - 如果 $l+1=r$，代价为 $x$。否则，代价为 $y$。 ## 输入格式 第一行一个整数 $t$ $(1\le t\le 600)$，表示数据组数。 每组第一行三个整数 $n$、$x$、$y$ $(\ 5\le n\le 3000\ ,1\le y\le x\le10^9)$，表示字符串长度，以及单次操作代价。 第二行 $a$，第三行 $b$，保证只包含0和1，长度为 $n$。 ## 输出格式 对于每组数据，一行一个整数，表示使 $a$ 等于 $b$ 的最小代价，或是 $-1$ 表示无解。

题目描述

This is the easy version of the problem. In this version, $ n \le 3000 $ , $ x \ge y $ holds. You can make hacks only if both versions of the problem are solved. You are given two binary strings $ a $ and $ b $ , both of length $ n $ . You can do the following operation any number of times (possibly zero). - Select two indices $ l $ and $ r $ ( $ l < r $ ). - Change $ a_l $ to $ (1 - a_l) $ , and $ a_r $ to $ (1 - a_r) $ . - If $ l + 1 = r $ , the cost of the operation is $ x $ . Otherwise, the cost is $ y $ . You have to find the minimum cost needed to make $ a $ equal to $ b $ or say there is no way to do so.

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 600 $ ) — the number of test cases. Each test case consists of three lines. The first line of each test case contains three integers $ n $ , $ x $ , and $ y $ ( $ 5 \le n \le 3000 $ , $ 1 \le y \le x \le 10^9 $ ) — the length of the strings, and the costs per operation. The second line of each test case contains the string $ a $ of length $ n $ . The string only consists of digits $ 0 $ and $ 1 $ . The third line of each test case contains the string $ b $ of length $ n $ . The string only consists of digits $ 0 $ and $ 1 $ . It is guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 3000 $ .

输出格式

For each test case, if there is no way to make $ a $ equal to $ b $ , print $ -1 $ . Otherwise, print the minimum cost needed to make $ a $ equal to $ b $ .

输入输出样例

输入样例 #1

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

输出样例 #1

8
-1
6
0

说明

In the first test case, selecting indices $ 2 $ and $ 3 $ costs $ 8 $ , which is the minimum possible cost. In the second test case, we cannot make $ a $ equal to $ b $ using any number of operations. In the third test case, we can perform the following operations: - Select indices $ 3 $ and $ 6 $ . It costs $ 3 $ , and $ a $ is 0101011 now. - Select indices $ 4 $ and $ 6 $ . It costs $ 3 $ , and $ a $ is 0100001 now. The total cost is $ 6 $ . In the fourth test case, we don't have to perform any operations.