Milk Exchange

문제

Farmer John's $NN$ $(1\le N\le 2\cdot {10}^5)(1\; \backslash leq\; N\; \backslash leq\; 2\; \backslash cdot\; 10^5)$ cows are lined up in a circle such that for each $ii$ in $1,2,\dots ,N-11,2,\backslash dots,N-1$, the cow to the right of cow $ii$ is cow $i+1i+1$, and the cow to the right of cow $NN$ is cow $11$. The $ii$th cow has a bucket with integer capacity $a_{i}a\_i$ $(1\le a_i\le {10}^9)(1\; \backslash leq\; a\_i\; \backslash leq\; 10^9)$ liters. All buckets are initially full.

Every minute, the cows exchange milk according to a string $s_1{s}_2\dots s_{N}s\_1s\_2\backslash dots\; s\_N$ consisting solely of the characters \text{‘L’} and \text{‘R’}. if the $ii$th cow has at least $11$ liter of milk, she will pass $11$ liter of milk to the cow to her left if s_i=\text{‘L’}, or to the right if s_i=\text{‘R’}. All exchanges happen simultaneously (i.e., if a cow has a full bucket but gives away a liter of milk but also receives a liter, her milk is preserved). If a cow's total milk ever ends up exceeding $a_{i}a\_i$, then the excess milk will be lost.

FJ wants to know: after $MM$ minutes $(1\le M\le {10}^9(1\; \backslash leq\; M\; \backslash leq\; 10^9$), what is the total amount of milk left among all cows?

입력

The first line contains $NN$ and $MM$.

The second line contains a string $s_1{s}_2\dots s_{N}s\_1s\_2\backslash dots\; s\_N$ consisting solely of the characters \text{‘L’} or \text{‘R’}, denoting the direction each cow will pass their milk in.

The third line contains integers $a_1,a_2,\dots ,a_{N}a\_1,\; a\_2,\; \backslash dots,\; a\_N$, the capacities of each bucket.

출력

Output an integer, the sum of milk among all cows after $MM$ minutes.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

3 1
RRL
1 1 1

2

5 20
LLLLL
3 3 2 3 3

14

9 5
RRRLRRLLR
5 8 4 9 3 4 9 5 4

38