D2. Zero-One (Hard Version)
dp; greedy
This is the hard version of this problem. In this version, \(n \le 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). 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 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 \le n \le 5000\), \(1 \le x, y \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 \(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. Select indices \(1\) and \(2\). It costs \(2\), and \(a\) is 110001 now. Select indices \(2\) and \(3\). It costs \(2\), and \(a\) is 101001 now. Select indices \(3\) and \(4\). It costs \(2\), and \(a\) is 100101 now. Select indices \(4\) and \(5\). It costs \(2\), and \(a\) is 100011 now. Select indices \(5\) and \(6\). It costs \(2\), and \(a\) is 100000 now. 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. 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 fifth test case, we can perform the following operations. Select indices \(1\) and \(6\). It costs \(4\), and \(a\) is 110000 now. Select indices \(2\) and \(3\). It costs \(3\), and \(a\) is 101000 now. The total cost is \(7\).In the sixth test case, we don't have to perform any operation.