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

Это простая версия задачи. В этой версии выполняется $$$n \le 3000$$$, $$$x \ge 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 600$$$) — количество наборов входных данных.

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

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

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

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

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

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

Пример
Входные данные
4
5 8 7
01001
00101
5 7 2
01000
11011
7 8 3
0111001
0100001
5 10 1
01100
01100
Выходные данные
8
-1
6
0
Примечание

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

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

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

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

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

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