题目描述

すぬけ君は、一列に並んだ無限個のマスからなる盤面を使って遊んでいます。 マスにはそれぞれ整数が振られていて、任意の整数 $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) そのようなマスが存在しない場合、 選んだコマと同じ色の空きマスをひとつを選びコマを置く

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

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

输入格式

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

$n$ $s$ $t$

输出格式

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

题目大意

有一个无限长的数轴，每个点有个颜色，$\leqslant 0$ 的点为白色，$>n$ 的为黑色，$[1,n]$ 由输入给出。在 $[1,n]$ 内有若干个需要标记的点。一次标记时需先选定一个颜色，如果存在这个颜色的未标记过的点，且存在与之相邻的点被标记过，则从中选择一个标记；否则，随意选择一个这个颜色的没有标记过的点标记。求把要求标记的点全部标记到的最小彪子次数。

3
wbb
o_o

2

4
wwww
o__o

3

9
bbwbwbwbb
_o_o_o_o_

5

17
wwwwbbbbbbbbwwwwb
__o__o_o_ooo__oo_

11

提示

制約

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

Sample Explanation 1

コマを置かなくてはならない白マスと黒マスをそれぞれ W と B で表して、 コマを置かなくてもよい白マスと黒マスをそれぞれ w と b で表すことにします。 盤面は次のようになります。 ...wwwwwwWbBbbbbb... 次の順番で置くと $2$ 回で条件を満たせます。 ...wwwwwwWbBbbbbb... 2 1 先に白マスに駒を置くと $3$ 回以上の操作が必要になることに注意してください。 ...wwwwwwWbBbbbbb... 123

Sample Explanation 2

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

Sample Explanation 3

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