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.


-----Input-----

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


-----Output-----

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


-----Examples-----

Input
6
5 8 9
01001
00101
6 2 11
000001
100000
5 7 2
01000
11011
7 8 3
0111001
0100001
6 3 4
010001
101000
5 10 1
01100
01100
Output
8
10
-1
6
7
0


-----Note-----

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.

Difficulty: HARD
Tags: Dynamic programming

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
import sys

def read(f):
	(n, x, y) = map(int, f.readline().split())
	a = f.readline().strip()
	b = f.readline().strip()
	zs = [i for (i, (c, d)) in enumerate(zip(a, b)) if c != d]
	return (zs, x, y)

def solve():
	(zs, x, y) = read(sys.stdin)
	if len(zs) % 2 != 0:
		print(-1)
		return
	if len(zs) == 0:
		print(0)
		return
	if x >= y:
		if len(zs) == 2 and zs[0] + 1 == zs[1]:
			print(min(x, 2 * y))
		else:
			print(len(zs) // 2 * y)
	else:
		f = []
		for (i, z) in enumerate(zs):
			if i == 0:
				cur = y
			elif i == 1:
				cur = min(2 * y, 2 * x * (z - zs[0]))
			else:
				cur = min(2 * x * (z - zs[i - 1]) + f[i - 2], y + f[i - 1])
			f.append(cur)
		print(f[-1] // 2)

def main():
	T = int(input().strip())
	for t in range(1, T + 1):
		solve()
main()


import sys
input = sys.stdin.readline

def solve():
	(n, x, y) = map(int, input().split())
	A = input().strip()
	B = input().strip()
	diff = []
	for i in range(n):
		if A[i] != B[i]:
			diff.append(i)
	m = len(diff)
	if x >= y:
		if m % 2:
			return -1
		elif m == 2:
			return y if diff[0] + 1 < diff[1] else min(2 * y, x)
		else:
			return y * (m // 2)
	elif m % 2:
		return -1
	elif m == 0:
		return 0
	else:
		dp = [[0, 0] for _ in range(m + 1)]
		dp[-1] = [0, float('inf')]
		dp[-2] = [float('inf'), y]
		for i in range(m - 2, -1, -1):
			dp[i][0] = min((diff[i + 1] - diff[i]) * x + dp[i + 2][0], dp[i + 1][1])
			dp[i][1] = min((diff[i + 1] - diff[i]) * x + dp[i + 2][1], y + dp[i + 1][0])
		return dp[0][0]
for _ in range(int(input())):
	print(solve())


from re import A

def cal(l):
	if len(l) == 0:
		return 0
	if len(l) == 2:
		if l[1] - l[0] == 1:
			return min(x, 2 * y)
		else:
			return min(y, x * (l[1] - l[0]))
	if y <= x:
		return len(l) // 2 * y
	else:
		(a, b) = (0, 0)
		for i in range(len(l) - 1):
			d = a
			c = max(a, b + max(y - x * (l[i + 1] - l[i]), 0))
			(a, b) = (c, d)
		return len(l) // 2 * y - a
for _ in range(int(input())):
	(n, x, y) = map(int, input().split())
	a = input()
	b = input()
	l = []
	for i in range(n):
		if a[i] != b[i]:
			l.append(i)
	if len(l) % 2 == 0:
		print(cal(l))
	else:
		print(-1)


def cal():
	if len(p) == 0:
		return 0
	if len(p) == 2:
		if p[1] == p[0] + 1:
			return min(x, 2 * y)
		else:
			return min(y, x * (p[1] - p[0]))
	if y <= x:
		return len(p) // 2 * y
	else:
		(a, b) = (0, 0)
		for i in range(len(p) - 1):
			d = a
			c = max(a, b + max(y - x * (p[i + 1] - p[i]), 0))
			(a, b) = (c, d)
		return len(p) // 2 * y - a
for jj in range(int(input())):
	(n, x, y) = [int(i) for i in input().split()]
	a = input()
	b = input()
	p = []
	for i in range(n):
		if a[i] != b[i]:
			p.append(i)
	if len(p) % 2 == 1:
		print(-1)
	else:
		print(cal())


from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 7)
for _ in range(int(input())):
	(n, x, y) = map(int, input().split())
	s1 = input()
	s2 = input()
	count = 0
	arr = []
	for i in range(n):
		if s1[i] != s2[i]:
			count += 1
			arr.append(i)
	if count == 0:
		print(0)
		continue
	if count & 1:
		print(-1)
		continue
	if x >= y:
		if count == 2 and arr[0] + 1 == arr[1]:
			if n >= 4:
				if 2 * y < x:
					print(2 * y)
				else:
					print(x)
			else:
				print(y)
		else:
			print(count // 2 * y)
		continue
	n = len(arr)

	@lru_cache(None)
	def fun(pre, i):
		if pre == -1:
			if i + 2 < n:
				return min(fun(1, i + 3) + (arr[i + 2] - arr[i + 1]) * x, fun(-1, i + 2) + min((arr[i + 1] - arr[i]) * x, y))
			else:
				return min((arr[i + 1] - arr[i]) * x, y)
		elif i + 1 < n:
			return min(fun(pre, i + 2) + (arr[i + 1] - arr[i]) * x, fun(-1, i + 1) + y)
		else:
			return y
	print(fun(-1, 0))