配点 : $1400$ 点

問題文

長さ $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$ に一致させるために必要な操作回数の最小値を求めてください。

制約

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

入力

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

$N$

$s$

$t$

出力

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

4
0011
0101

4

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

1
0
0

0

8
00110011
10101010

10