Description

输入一个长度为 n 的字符串 s ，只包含两种字符 A,B ，已知它某 m 位上的字符，你想要把它填充完整使得相邻字母相同的次数尽量少，问这个最少次数。

（其中 n≤1e9 ， m≤50 ）

Input

第一行两个数 n,m ，表示字符串长度，已知位置数。 第二行 m 个数 pos[i] ； 第三行一个长度为 m 的字符串 val[i] ，表示 s[pos[i]]=val[i] 。 保证 pos[i] 两两不同， 1≤pos[i]≤n ， val[i]=′A′or′B′ 。

Output

一个数，表示最少次数。

Samples

3 2

1 3

AB

1