Дівчата
Обмеження: 2 сек., 256 МіБ
Сеньйор знає 2n дівчат. Він вишикував їх у колону з двох рядів по n дівчат у кожному ряді, по дві дівчини в кожному стовпці. Ряди розташовані один навпроти одного. Дві дівчини будемо вважати сусідніми, якщо одна з них стоїть одразу біля іншої в тому ж рядку або стовпці.
У кожної дівчини спочатку колір волосся або рудий, або чорний. За один хід Сеньйор може зробити одну з таких дій.
Вибрати довільну дівчину. Вона переконає одну із сусідніх дівчат (на вибір Сеньйора) перефарбувати волосся в її колір.
Вибрати довільну дівчину, а також її сусідку зверху або знизу. Крім цього, вибрати один напрям (вліво або вправо). Кожна з вибраних дівчат переконає сусідню (у вибраному напрямі) дівчину перефарбувати колір волосся в її колір.
Вибрати будь-яку послідовну множину дівчат з одного з рядів. Кожна з вибраних дівчат переконає сусідню дівчину з іншого ряду перефарбувати колір волосся в її колір.
Сеньйор любить рудих дівчат. Допоможіть йому знайти мінімальну кількість ходів необхідну для того, щоб усі дівчата стали рудими.
Вхідні дані
У першому рядку задано одне ціле число n — кількість дівчат в одному ряді.
У другому рядку задано рядок із символів R та
B — кольори волосся дівчат у першому ряді.
У третьому рядку задано кольори волосся дівчат у другому ряді в аналогічному форматі.
Символ R означає руду дівчину, а символ B —
дівчину із чорним волоссям.
Гарантується, що на початку Сеньйор знайомий хоча б з одною рудою дівчиною.
Вихідні дані
У єдиному рядку виведіть ціле число — відповідь на задачу.
Обмеження
1≤n≤50.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 3 RBR BRB | 2 |
Примітки
Одна з оптимальних стратегій.
Вибрати другу дівчину з другого ряду. Вона переконає другу дівчину з першого ряду перефарбувати волосся в рудий. Після цього всі дівчата з першого ряду стануть рудими.
Вибрати всіх дівчат із першого ряду. Вони переконають усіх дівчат з другого ряду перефарбувати волосся в рудий.