CF1733D1 Zero-One (Easy Version)

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 $ .

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.