E - Less than 3

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1400

問題文

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

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

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

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

制約

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

入力

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

N
s
t

出力

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


入力例 1

4
0011
0101

出力例 1

4

例えば、00111011100111010101 と操作を行えばよいです。


入力例 2

1
0
0

出力例 2

0

入力例 3

8
00110011
10101010

出力例 3

10

Score : 1400 points

Problem Statement

You are given strings s and t, both of length N. s and t consist of 0 and 1. Additionally, in these strings, the same character never occurs three or more times in a row.

You can modify s by repeatedly performing the following operation:

  • Choose an index i (1 \leq i \leq N) freely and invert the i-th character in s (that is, replace 0 with 1, and 1 with 0), under the condition that the same character would not occur three or more times in a row in s after the operation.

Your objective is to make s equal to t. Find the minimum number of operations required.

Constraints

  • 1 \leq N \leq 5000
  • The lengths of s and t are both N.
  • s and t consists of 0 and 1.
  • In s and t, the same character never occurs three or more times in a row.

Input

Input is given from Standard Input in the following format:

N
s
t

Output

Find the minimum number of operations required to make s equal to t. It can be proved that the objective is always achievable in a finite number of operations.


Sample Input 1

4
0011
0101

Sample Output 1

4

One possible solution is 00111011100111010101.


Sample Input 2

1
0
0

Sample Output 2

0

Sample Input 3

8
00110011
10101010

Sample Output 3

10