Сумасшедший ученый
Сумасшедший ученый
Фермер Джон упорядочил n своих коров, каждая из которых имеет одну из двух пород Holsteins или Guernseys. Он зафиксировал этот порядок в виде строки из n символов, каждый из которых либо H, либо G соответственно. К несчастью, когда коровы прибыли на ферму и он снова их выстроил, они образовали строку, отличную от исходной.
Назовём эти две строки a и b, где a — исходная строка, которую он хотел увидеть, b — строка которая получилась по прибытию коров. Фермер Джон попросил помощи у кузена Бена.
После нескольких месяцев работы, Бен создал замечательную машину MCBF-3000, которая способна взять любую подстроку и поменять в ней все G на H, а все H на G. Теперь Фермер Джон хочет узнать минимальное количество применений этой машины, которые позволят превратить строку b в строку a. Помогите Фермеру Джону.
Входные данные
Первая строка содержит n~(1 \le n \le 1000), следующие две строки содержат строки a и b. Каждая из строк состоит только из символов H и G.
Выходные данные
Выведите минимальное количество раз применения машины MCBF-3000 для трансформации строки b в строку a.
Пример
7 GHHHGHH HHGGGHH
2