D2. Ноль-один (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это усложненная версия задачи. В этой версии выполняется $$$n \le 5000$$$, и нет ограничений между $$$x$$$ и $$$y$$$. Вы можете делать взломы только в том случае, если обе версии задачи решены.

Вам даны две бинарные строки $$$a$$$, $$$b$$$ длины $$$n$$$. Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):

  • Выберите два индекса $$$l$$$ и $$$r$$$ ($$$l < r$$$).
  • Замените $$$a_l$$$ на $$$(1 - a_l)$$$ и $$$a_r$$$ на $$$(1 - a_r)$$$.
  • Если $$$l + 1 = r$$$, стоимость операции равна $$$x$$$. В противном случае стоимость равна $$$y$$$.

Вы должны найти минимально необходимую стоимость для превращения $$$a$$$ в $$$b$$$, или сказать, что это невозможно сделать.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из трех строк. Первая строка содержит три целых числа $$$n$$$, $$$x$$$ и $$$y$$$ ($$$5 \le n \le 5000$$$, $$$1 \le x, y \le 10^9$$$) — длина строк и операций.

Вторая строка каждого набора входных данных содержит строку $$$a$$$ длины $$$n$$$. Строка состоит только из цифр $$$0$$$ и $$$1$$$.

Третья строка каждого набора входных данных содержит строку $$$b$$$ длины $$$n$$$. Строка состоит только из цифр $$$0$$$ и $$$1$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5000$$$.

Выходные данные

Для каждого набора входных данных, если нет способа сделать $$$a$$$ равным $$$b$$$, выведите $$$-1$$$. В противном случае выведите минимальную стоимость, чтобы $$$a$$$ равнялось $$$b$$$. Ответ следует печатать по одному в строке.

Пример
Входные данные
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
Выходные данные
8
10
-1
6
7
0
Примечание

В первом примере можно выбрать индексы $$$2$$$ и $$$3$$$, стоимость операции будет равна $$$8$$$.

Во втором примере мы можем выполнить следующие операции.

  • Выберите индексы $$$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$$$.

В третьем примере не возможно сделать $$$a$$$ равным $$$b$$$ при помощи этой операции.

В четвертом примере, мы можем выполнить следующие операции.

  • Выберите индексы $$$3$$$ и $$$6$$$. Это стоит $$$3$$$, и после этого $$$a$$$ равно 0101011.
  • Выберите индексы $$$4$$$ и $$$6$$$. Это стоит $$$3$$$, и после этого $$$a$$$ равно 0100001.

Общая стоимость $$$6$$$.

В пятом примере, мы можем выполнить следующие операции.

  • Выберите индексы $$$1$$$ и $$$6$$$. Это стоит $$$4$$$, и после этого $$$a$$$ равно 110000.
  • Выберите индексы $$$2$$$ и $$$3$$$. Это стоит $$$3$$$, и после этого $$$a$$$ равно 101000.

Общая стоимость $$$7$$$.

В шестом примере строки изначально равны, поэтому оптимально не выполнять никаких операции.