题目描述

Snuke正在玩一个由无限多个方块组成的排列在一行上的棋盘。每个方块上有一个整数；对于每个整数$i$，方块$i$和方块$i+1$是相邻的。此外，每个方块上都被涂成白色或黑色。

一个长度为$n$的字符串$s$，由w和b组成，表示此棋盘上方块的颜色，具体规则如下：

• 当$i=1, 2, \dots, n$时，如果$s$的第$i$个字符是w，方块$i$是白色；如果该字符是b，方块$i$是黑色；
• 当$i \leq 0$时，方块$i$是白色；
• 当$i > n$时，方块$i$是黑色。

Snuke有无限多个白子和无限多个黑子。他将按照以下规则将这些棋子放在棋盘上：

• (1) 选择一种颜色的棋子。
• (2) 在已有棋子的方块相邻的方块中，寻找与选择的棋子颜色相同的方块。
  • (2a) 如果存在这样的方块，选择其中一个并在其上放置棋子；
  • (2b) 如果不存在这样的方块，选择与选择的棋子颜色相同的方块，并在其上放置棋子。

棋盘最初没有任何棋子。

给定一个长度为$n$的字符串$t$，由o和_组成。找出Snuke需要在棋盘上放置的最少棋子数量，使得在方块$1,..,n$中的每个方块$i$上都有一个棋子，并且$t$的第$i$个字符是o。保证$t$至少有一个o。

约束条件

• $1 \leq n \leq 10^5$
• $|s| = |t| = n$
• $s$由w和b组成。
• $t$由o和_组成。
• $t$至少有一个o。

输入

输入以以下格式从标准输入中给出：

$n$ $s$ $t$

输出

输出Snuke需要放置在棋盘上的最少棋子数量。

示例输入1

3
wbb
o_o

示例输出1

2

用W表示需要放置一个白棋子的方块，用B表示需要放置一个黑棋子的方块，用w表示不需要放置棋子的白方块，用b表示不需要放置棋子的黑方块。

我们有如下棋盘：

...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