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