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$。 保证 $n$ 的总和不超过 $5000$。

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

在第 $1$ 组测试数据中，选择第 $2$ 和第 $3$ 个位置，代价为 $8$，这是最小可能的代价。 在第 $2$ 组测试数据中，我们执行如下步骤。 - 选择第 $1$ 和第 $2$ 个位置，代价为 $2$，$a$ 现在是 110001。 - 选择第 $2$ 和第 $3$ 个位置，代价为 $2$，$a$ 现在是 101001。 - 选择第 $3$ 和第 $4$ 个位置，代价为 $2$，$a$ 现在是 100101。 - 选择第 $4$ 和第 $5$ 个位置，代价为 $2$，$a$ 现在是 100011。 - 选择第 $5$ 和第 $6$ 个位置，代价为 $2$，$a$ 现在是 100000。 总花费为 $10$。 在第 $3$ 组测试数据中，我们无法操作使 $a$ 等于 $b$。 在第 $4$ 组测试数据中，我们执行如下步骤。 - 选择第 $3$ 和第 $6$ 个位置，代价为 $3$，$a$ 现在是 0101011。 - 选择第 $4$ 和第 $6$ 个位置，代价为 $3$，$a$ 现在是 0100001。 总花费为 $6$。 在第 $5$ 组测试数据中，我们执行如下步骤。 - 选择第 $1$ 和第 $6$ 个位置，代价为 $4$，$a$ 现在是 110000。 - 选择第 $2$ 和第 $3$ 个位置，代价为 $3$，$a$ 现在是 101000。 总花费为 $7$。 在第 $6$ 组测试数据中，我们无需执行任何操作。