题目描述

现有一字符串s，只包含两种字符 'A', 'B'，已知它某些位置上的字符，你想要把它填充完整使得相邻字母相同的次数尽量少，问这个最少次数。

输入格式

共三行，
第一行两个整数 $n,m$，分别表示字符串 $s$ 长度，已知位置数；
第二行 $m$ 个整数 $pos[i]$（$1 \le pos[i] \le n$ 且两两不同），以空格分开，表示已知的位置；
第三行一个长度为 $m$ 的字符串（只包含'A', 'B'），其中第 $i$ 个字符为 $val[i]$，表示 $s[pos[i]]=val[i]$。

输出格式

一行一个整数，表示最少次数

样例 #1

样例输入 #1

3 2
1 3
AB

样例输出 #1

1

提示

1 < n < 10^9，1 <e m < 50