Это простая версия задачи. В этой версии выполняется \(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\), или сказать, что это невозможно сделать.
Выходные данные
Для каждого набора входных данных, если нет способа сделать \(a\) равным \(b\), выведите \(-1\). В противном случае выведите минимальную стоимость, чтобы \(a\) равнялось \(b\).
Примечание
В первом примере можно выбрать индексы \(2\) и \(3\), стоимость операции будет равна \(8\).
Во втором примере невозможно сделать \(a\) равным \(b\) при помощи этой операции.
В третьем примере мы можем выполнить следующие операции.
- Выберите индексы \(3\) и \(6\). Это стоит \(3\), и после этого \(a\) равно 0101011.
- Выберите индексы \(4\) и \(6\). Это стоит \(3\), и после этого \(a\) равно 0100001.
Общая стоимость \(6\).
В четвертом примере строки изначально равны, поэтому оптимально не выполнять никаких операции.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|