Ёлочная гирлянда состоит из n лампочек, пронумерованных от 1 до n. Каждая лампочка либо горит (обозначим «1»), либо не горит («0»). Текущее состояние гирлянды задано строкой a.
Монтажник Егор хочет, чтобы гирлянда выглядела по-праздничному — в виде строки b (тоже из нулей и единиц, той же длины n). Менять строку b нельзя — это «образец».
С гирляндой a Егор может выполнять две операции:
- Переключить одну лампочку. Выбрать позицию
i (1 ≤ i ≤ n) и поменять её состояние (0 → 1 или 1 → 0). Стоимость такой операции — 1 рубль.
- Поменять местами две лампочки. Выбрать две позиции
i и j (1 ≤ i, j ≤ n) и поменять состояния этих лампочек местами. Стоимость такой операции — |i - j| рублей, то есть расстояние между позициями.
Помогите Егору найти минимальную суммарную стоимость, с которой можно превратить гирлянду a в гирлянду b.
Формат входных данных
В первой строке — целое число n (1 ≤ n ≤ 106) — количество лампочек в гирлянде.
Во второй строке — строка a длины n, состоящая только из символов «0» и «1», — текущее состояние гирлянды.
В третьей строке — строка b длины n, состоящая только из символов «0» и «1», — желаемое состояние гирлянды.
Формат выходных данных
Одно целое число — минимальная суммарная стоимость, которую нужно заплатить, чтобы превратить a в b.
| № | Входные данные | Выходные данные |
|
1
|
3
100
001
|
2
|
|
2
|
4
0101
0011
|
1
|