题目描述

長さ $N$ の文字列 $s$ および $t$ が与えられます。 $s$ および $t$ は 0 と 1 からなります。 また、$s$ および $t$ において、同一の文字が $3$ 個以上連続する箇所はありません。

あなたは次の操作を繰り返し行い、$s$ を書き換えていくことができます。

• 添字 $i$ ($1\ \leq\ i\ \leq\ N$) を任意に選び、$s$ の $i$ 文字目を反転する (すなわち、0 を 1 へ、1 を 0 へ書き換える)。 ただし、操作後の $s$ において、同一の文字が $3$ 個以上連続する箇所があってはならない。

あなたの目標は $s$ を $t$ に一致させることです。 $s$ を $t$ に一致させるために必要な操作回数の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $s$ $t$

输出格式

$s$ を $t$ に一致させるために必要な操作回数の最小値を出力せよ。なお、有限回の操作で目的は必ず達成可能であることが証明できる。

题目大意

给定两个长度为 $n$ 的 01 串 $s,t$ , 串的连续段长度不超过 $2$ , 每次操作可以把 $s$ 的一个位置反转, 要求操作后连续段长度仍不超过 $2$ , 求使得 $s,t$ 相等的最少操作次数.

$n\leqslant 5000$

4
0011
0101

4

1
0
0

0

8
00110011
10101010

10

提示

制約

• $1\ \leq\ N\ \leq\ 5000$
• $s$ および $t$ の長さは $N$ である。
• $s$ および $t$ は 0 と 1 からなる。
• $s$ および $t$ において、同一の文字が $3$ 個以上連続する箇所はない。

Sample Explanation 1

例えば、0011 → 1011 → 1001 → 1101 → 0101 と操作を行えばよいです。