配点 : $900$ 点

問題文

すぬけ君は、一列に並んだ無限個のマスからなる盤面を使って遊んでいます。 マスにはそれぞれ整数が振られていて、任意の整数 $i$ についてマス $i$ と マス $i+1$ は隣り合っています。 また、それぞれのマスは白か黒で塗られています。

この盤面のマスの色は、長さ $n$ の w, b からなる文字列 $s$ によって以下のように表されます。

• $i = 1, 2, \dots, n$ について、$s$ の $i$ 文字目が w であるときマス $i$ は白色であり、b であるときマス $i$ は黒色である
• $i \leq 0$ について、マス $i$ は白色である
• $i > n$ について、マス $i$ は黒色である

すぬけ君は白いコマと黒いコマをそれぞれ無限個持っています。すぬけ君は次の手順でこれらのコマを盤面に置いていきます。

• (1) 好きな色のコマを選ぶ
• (2) すでにコマが置かれているマスと隣り合ったマスのうち、選んだコマと同じ色の空きマスを探す- (2a) そのようなマスが存在する場合、そのうちひとつを選びコマを置く
  • (2b) そのようなマスが存在しない場合、 選んだコマと同じ色の空きマスをひとつを選びコマを置く
• (2a) そのようなマスが存在する場合、そのうちひとつを選びコマを置く
• (2b) そのようなマスが存在しない場合、 選んだコマと同じ色の空きマスをひとつを選びコマを置く

最初、盤面にコマは置かれていません。

長さ $n$ の o, _ からなる文字列 $t$ が与えられます。マス $1,..,n$ のうち、$t$ の $i$ 文字目が o であるマス $i$ すべてにコマを置くためには、最小でいくつコマを置く必要がありますか？ $t$ が $1$ 文字以上の o を含むことが保証されます。

制約

• $1 \leq n \leq 10^5$
• $|s| = |t| = n$
• $s$ は w と b のみからなる
• $t$ は o と _ のみからなる
• $t$ は o を $1$ 文字以上含む

入力

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

$n$

$s$

$t$

出力

すぬけ君が置く必要のあるコマの数の最小値を出力せよ。

3
wbb
o_o

2

コマを置かなくてはならない白マスと黒マスをそれぞれ W と B で表して、 コマを置かなくてもよい白マスと黒マスをそれぞれ w と b で表すことにします。 盤面は次のようになります。

...wwwwwwWbBbbbbb...

次の順番で置くと $2$ 回で条件を満たせます。

...wwwwwwWbBbbbbb...
         2 1

先に白マスに駒を置くと $3$ 回以上の操作が必要になることに注意してください。

...wwwwwwWbBbbbbb...
         123

4
wwww
o__o

3

次の順番で置くと $3$ 回で条件を満たせます。

...wwwwwWwwWbbbbb...
        1  32

9
bbwbwbwbb
_o_o_o_o_

5

次の順番で置くと $5$ 回で条件を満たせます。

...wwwwwbBwBwBwBbbbbbb...
        12 3 4 5

17
wwwwbbbbbbbbwwwwb
__o__o_o_ooo__oo_

11