Zero-One (Easy Version) solution codeforces

This is the easy version of the problem. In this version, 𝑥𝑦x≥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 𝑎𝑙al to (1𝑎𝑙)(1−al), and 𝑎𝑟ar to (1𝑎𝑟)(1−ar).
  • If 𝑙+1=𝑟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.

Zero-One (Easy Version) solution codeforces

Input

The first line contains one integer 𝑡t (1𝑡6001≤t≤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𝑛30005≤n≤30001𝑦𝑥1091≤y≤x≤109) — 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 00 and 11.

The third line of each test case contains the string 𝑏b of length 𝑛n. The string only consists of digits 00 and 11.

It is guaranteed that the sum of 𝑛n over all test cases doesn’t exceed 30003000.

Output

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

Example

input

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

01100

Zero-One (Easy Version) solution codeforces

01100

output

Copy
8
-1
6
0
Note

In the first test case, selecting indices 22 and 33 costs 88, 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 33 and 66. It costs 33, and 𝑎a is 0101011 now.
  • Select indices 44 and 66. It costs 33, and 𝑎a is 0100001 now.

The total cost is 66.

In the fourth test case, we don’t have to perform any operations.

Solution – CLICK HERE

Leave a Comment

Your email address will not be published.