CF1733D2 Zero-One (Hard Version)

两个长度为 $n$ 的二进制字符串 $a$ 和 $b$。你可以进行如下操作若干次（可以为0次）： - 选两个数 $l,r(l

第一行一个整数 $t$ $(1\le t\le 1000)$，表示数据组数。 每组第一行三个整数 $n$、$x$、$y$ $(5\le n\le 5000,1\le x,y\le10^9)$，表示字符串长度，以及单次操作代价。 第二行 $a$，第三行 $b$，保证只包含 $0$ 和 $1$，长度为 $n$。

对于每组数据，一行一个整数，表示使 $a$ 等于 $b$ 的最小代价，或是 $-1$ 表示无解。

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.