31649번 - Milk Exchange 다국어

문제

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

Every minute, the cows exchange milk according to a string $s_1s_2\dots s_N$ consisting solely of the characters $\text{‘L’}$ and $\text{‘R’}$. if the $i$th cow has at least 1ドル$ liter of milk, she will pass 1ドル$ 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,ドル then the excess milk will be lost.

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

입력

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

The second line contains a string $s_1s_2\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,ドル the capacities of each bucket.

출력

Output an integer, the sum of milk among all cows after $M$ 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++).

제한

힌트