Migrated from Lutece 1570 C0ntest

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

In the Gothic Club, there are $N$ vip members labeled from $1$ to $N$, and $M$ normal members labeled from $1$ to $M$.

There is a rating rank of the vip members and a rating rank of the normal members.

Today, a contest is hold between the vip members and the normal members. Each vip member plays a game with each normal member, the contest result is given to you as a $N \times M$ matrix.

You need to construct a final rank contains both vip members and normal members such that :

• For two vip members $i$ and $j$, if $i$ has higher rank than $j$ in the vip rating rank, then $i$ must have higher rank than $j$ in the final rank.
• For two normal members $i$ and $j$, if $i$ has higher rank than $j$ in the normal rating rank, then $i$ must have higher rank than $j$ in the final rank.
• For a vip member $i$ and a normal member $j$, if $i$ wins $j$ in the contest, then $i$ must have higher rank then $j$ in the final rank.
• For a normal member $i$ and a vip member $j$, if $i$ wins $j$ in the contest, then $i$ must have higher rank then $j$ in the final rank.

It may can not construct a final rank which contains all the vip members and normal members, now you need to delete some normal members such that we can construct a final rank which contains all the last members.

Calculating the minimum number of the normal members you have to delete.

Input

The first line contains two integers $N$ and $M$.

The second line contains $N$ integers $x_1, x_2, \dots, x_N$ denotes the rating rank of the vip members, $x_i$ is the label of the vip member who stays at the $i_{th}$ place in the rank.

The third line contains $M$ integers $y_1, y_2, \dots, y_M$ denotes the rating rank of the normal members in the same format.

The next $N$ lines form a matrix denotes the contest result, each line contains $M$ characters.

$$\begin{array}{cccc} s_{11} & s_{12} & \dots & s_{1M} \\ s_{21} & s_{22} & \dots & s_{2M} \\ \vdots & \vdots & \vdots & \vdots \\ s_{N1} & s_{N2} & \dots & s_{NM} \\ \end{array} $$$$s_{ij}= \begin{cases} W& \text{vip member i wins the game to the normal member j}\\ L& \text{vip member i loses the game to the normal member j}\\ N& \text{vip member i draws the game to the normal member j}\\ \end{cases} $$

$1 \leq N, M \leq 1000$, $1 \leq x_i \leq N$, $1 \leq y_i \leq M$, $x_i$ and $y_i$ form two permutations.

Output

The minimum number of the normal members you have to delete.

Samples

3 2
1 2 3
1 2
WW
WL
LL

1

Resources

The 15th UESTC Programming Contest Final