Вам даны две бинарные строки \(a\) и \(b\) равной длины. Вы можете производить над строкой \(a\) следующие операции:
- Поменять два бита на позициях \(i\) и \(j\) соответственно (\(1 \le i, j \le n\)), стоимость этой операции составляет \(|i - j|\), то есть модуль разницы \(i\) и \(j\).
- Выбрать произвольную позицию \(i\) (\(1 \le i \le n\)) и инвертировать (заменить \(0\) на \(1\) или \(1\) на \(0\)) значение бита на этой позиции. Стоимость этой операции равна \(1\)
Найдите минимальную стоимость, которую нужно потратить, чтобы сделать строку \(a\) равной строке \(b\). Менять строку \(b\) не разрешается.
Выходные данные
Выведите минимальную стоимость, которая требуется, чтобы превратить строку \(a\) в \(b\).
Примечание
В первом примере одним из оптимальных способов является следующий: нужно инвертировать позицию \(1\), а затем позицию \(3\). Тогда строка \(a\) меняется следующим образом: «100» \(\to\) «000» \(\to\) «001». Стоимость составляет \(1 + 1 = 2\).
Другим оптимальным решением является следующее: можно поменять местами позиции \(1\) и \(3\), тогда строка \(a\) меняется как «100» \(\to\) «001», стоимость также равна \(|1 - 3| = 2\).
Во втором примере оптимальным решением является следующее: нужно поменять местами позиции \(2\) и \(3\), тогда строка \(a\) меняется как «0101» \(\to\) «0011». Стоимость равна \(|2 - 3| = 1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
100
001
|
2
|
|
2
|
4
0101
0011
|
1
|