Contest Duration: - (local time) (120 minutes) Back to Home
F - 1D Kingdom Builder /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

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

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

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

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

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

### 制約

• 1 \leq n \leq 10^5
• |s| = |t| = n
• swb のみからなる
• to_ のみからなる
• to1 文字以上含む

### 入力

n
s
t


### 出力

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

### 入力例 1

3
wbb
o_o


### 出力例 1

2


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

...wwwwwwWbBbbbbb...


...wwwwwwWbBbbbbb...
2 1


...wwwwwwWbBbbbbb...
123


### 入力例 2

4
wwww
o__o


### 出力例 2

3


...wwwwwWwwWbbbbb...
1  32


### 入力例 3

9
bbwbwbwbb
_o_o_o_o_


### 出力例 3

5


...wwwwwbBwBwBwBbbbbbb...
12 3 4 5


### 入力例 4

17
wwwwbbbbbbbbwwwwb
__o__o_o_ooo__oo_


### 出力例 4

11


Score : 900 points

### Problem Statement

Snuke is playing with a board composed of infinitely many squares lining up in a row. Each square has an assigned integer; for each integer i, Square i and Square i+1 are adjacent. Additionally, each square is painted white or black.

A string s of length n consisting of w and b represents the colors of the squares of this board, as follows:

• For each i = 1, 2, \dots, n, Square i is white if the i-th character of s is w, and black if that character is b;
• For each i \leq 0, Square i is white;
• For each i > n, Square i is black.

Snuke has infinitely many white pieces and infinitely many black pieces. He will put these pieces on the board as follows:

• (1) Choose a piece of the color of his choice.
• (2) Among the squares adjacent to a square that already contains a piece, look for squares of the same color as the chosen piece.
• (2a) If there are such squares, choose one of them and put the piece on it;
• (2b) if there is no such square, choose a square of the same color as the chosen piece and put the piece on it.

The board initially has no piece on it.

You are given a string t of length n consisting of o and _. Find the minimum number of pieces Snuke needs to put on the board to have a piece on every square i among Squares 1,..,n such that the i-th character of t is o. It is guaranteed that t has at least one occurrence of o.

### Constraints

• 1 \leq n \leq 10^5
• |s| = |t| = n
• s consists of w and b.
• t consists of o and _.
• t has at least one occurrence of o.

### Input

Input is given from Standard Input in the following format:

n
s
t


### Output

Print the minimum number of pieces Snuke needs to put on the board.

### Sample Input 1

3
wbb
o_o


### Sample Output 1

2


Let us use W to represent a white square that needs a piece on it, B to represent a black square that needs a piece on it, w to represent a white square that does not need a piece on it, and b to represent a black square that does not need a piece on it.

We have the following board:

...wwwwwwWbBbbbbb...


If we put pieces in the following order, two pieces is enough:

...wwwwwwWbBbbbbb...
2 1


Note that if we put a piece on the white square first, we will need three or more pieces:

...wwwwwwWbBbbbbb...
123


### Sample Input 2

4
wwww
o__o


### Sample Output 2

3


If we put pieces in the following order, three pieces is enough:

...wwwwwWwwWbbbbb...
1  32


### Sample Input 3

9
bbwbwbwbb
_o_o_o_o_


### Sample Output 3

5


If we put pieces in the following order, five pieces is enough:

...wwwwwbBwBwBwBbbbbbb...
12 3 4 5


### Sample Input 4

17
wwwwbbbbbbbbwwwwb
__o__o_o_ooo__oo_


### Sample Output 4

11