B"This is the hard version of this problem. In this version, n <= 5000 holds, and this version has no restriction between x and y . 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). 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 <= t <= 1000 ) -- 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 <= n <= 5000 , 1 <= x, y <= 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 5000 . 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. In the second test case, we can perform the following operations. The total cost is 10 . In the third test case, we cannot make a equal to b using any number of operations. In the fourth test case, we can perform the following operations. The total cost is 6 . In the fifth test case, we can perform the following operations. The total cost is 7 . In the sixth test case, we don't have to perform any operation. "...