该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在一款名为“世界贸易”的游戏中，全球有 $N$（$1\le N\le 2\cdot 10^5$）个城市组成了一个密切合作的环形网络，目的是为了优化资源分配和交换。这个网络的特点是，对于编号为 $1,2,\ldots,N-1$ 的每个城市，其右侧直接相邻的城市是编号为 $i+1$ 的城市，而编号为 $N$ 的城市的右侧直接相邻的城市是编号为 $1$ 的城市。第 $i$ 个城市有一个容量为整数 $a_i$（$1\le a_i\le 10^9$）单位的储存设施。初始时，所有城市的储存设施都装满了资源。

游戏每进行一分钟，根据一个由字符 A 和 B 组成的策略序列 $s_1s_2\ldots s_N$，城市间会进行资源交换。当第 $i$ 个城市至少有 $1$ 单位资源时，如果 $s_i=\texttt{A}$，它会向它左侧的城市传输 $1$ 单位资源；如果 $s_i=\texttt{B}$，则向右侧的城市传输。所有城市的资源传输是同时进行的。如果某城市在这一过程中既发送又接收到等量的资源，其资源量则保持不变。如果任何时刻一个城市的资源超出其储存容量 $a_i$，超出部分将会丢失。

游戏设计者想要计算：经过 $M$ 分钟（$1\le M\le 10^9$）的资源交换后，所有城市总共还剩下多少单位的资源？

输入格式

输入的第一行包含 $N$ 和 $M$。

第二行包含一个由字符 A 或 B 组成的字符串 $s_1s_2\ldots s_N$，代表每个城市的资源传输策略。

第三行包含整数 $a_1,a_2,\ldots,a_N$，代表每个城市储存设施的容量。

输出格式

输出一个整数，为 $M$ 分钟后所有城市总共剩余的资源量。

注意：相关计算可能需要使用 64 位整数（例如，在 C/C++ 中的 long long 类型）。

样例 #1

输入

3 1
BBA
1 1 1

输出

2

解释

城市 1 和城市 2 互相传递了 1 单位资源，因此它们的资源得以保留。当城市 3 将资源传递给城市 2 时，城市 2 的储存设施会溢出，导致在一分钟后损失了 1 单位资源。

样例

输入

5 20
AAAAA
3 3 2 3 3

输出

14

解释

每个城市都将 1 单位资源传递给左侧的城市，并从右侧的城市接收 1 单位资源，因此不论过了多长时间，所有资源都得以保存。

样例

输入

9 5
BBBABBAAB
5 8 4 9 3 4 9 5 4

输出

38

解释

初始时，共有 51 单位资源。5 分钟后，城市 3、城市 6 和城市 7 将分别损失 5、3 和 5 单位资源。因此，总共还剩下 38 单位

数据范围：

10% - 80%: N,M <=1000

100% ：数据无限制