Score : $425$ points

问题陈述

有 $N+2$ 个单元格排成一行。设单元格 $i$ 表示从左边数起的第 $i$ 个单元格。

从单元格 $1$ 到单元格 $N$ 的每个单元格中都放置了一块石头。 对于每个 $1 \leq i \leq N$，如果 $S_i$ 是 W，则单元格 $i$ 中的石头是白色的；如果 $S_i$ 是 B，则单元格 $i$ 中的石头是黑色的。 单元格 $N+1$ 和单元格 $N+2$ 是空的。

你可以执行以下操作任意次数（可能为零）：

• 选择一对相邻的单元格，这两个单元格都包含石头，并将这两块石头移动到空的两个单元格中，同时保持它们的顺序。 更准确地说，选择一个整数 $x$，使得 $1 \leq x \leq N+1$ 并且单元格 $x$ 和单元格 $x+1$ 都包含石头。设 $k$ 和 $k+1$ 是空的两个单元格。将单元格 $x$ 和单元格 $x+1$ 中的石头分别移动到单元格 $k$ 和单元格 $k+1$。

确定是否可能达到以下状态，如果可能，找到所需的最小操作次数：

• 从单元格 $1$ 到单元格 $N$ 的每个单元格都包含一块石头，对于每个 $1 \leq i \leq N$，如果 $T_i$ 是 W，则单元格 $i$ 中的石头是白色的；如果 $T_i$ 是 B，则单元格 $i$ 中的石头是黑色的。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

There are $N+2$ cells arranged in a row. Let cell $i$ denote the $i$-th cell from the left.

There is one stone placed in each of the cells from cell $1$ to cell $N$.
For each $1 \leq i \leq N$, the stone in cell $i$ is white if $S_i$ is W, and black if $S_i$ is B.
Cells $N+1$ and $N+2$ are empty.

You can perform the following operation any number of times (possibly zero):

• Choose a pair of adjacent cells that both contain stones, and move these two stones to the empty two cells while preserving their order.
  More precisely, choose an integer $x$ such that $1 \leq x \leq N+1$ and both cells $x$ and $x+1$ contain stones. Let $k$ and $k+1$ be the empty two cells. Move the stones from cells $x$ and $x+1$ to cells $k$ and $k+1$, respectively.

Determine if it is possible to achieve the following state, and if so, find the minimum number of operations required:

• Each of the cells from cell $1$ to cell $N$ contains one stone, and for each $1 \leq i \leq N$, the stone in cell $i$ is white if $T_i$ is W, and black if $T_i$ is B.

Constraints

• $2 \leq N \leq 14$
• $N$ is an integer.
• Each of $S$ and $T$ is a string of length $N$ consisting of B and W.

Input

The input is given from Standard Input in the following format:

$N$

$S$

$T$

Output

If it is possible to achieve the desired state, print the minimum number of operations required. If it is impossible, print -1.

Sample Input 1

6
BWBWBW
WWWBBB

Sample Output 1

4

Using . to represent an empty cell, the desired state can be achieved in four operations as follows, which is the minimum:

• BWBWBW..
• BW..BWBW
• BWWBB..W
• ..WBBBWW
• WWWBBB..

Sample Input 2

6
BBBBBB
WWWWWW

Sample Output 2

-1

Sample Input 3

14
BBBWBWWWBBWWBW
WBWWBBWWWBWBBB

Sample Output 3

7