Problem Description

Farmer John has \( N \) (\( 1 \le N \le 2 \cdot 10^5 \)) cows arranged in a circle such that for each \( i \) in \( 1, 2, \ldots, 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 \). Each cow \( i \) has a bucket with an integer capacity \( a_i \) (\( 1 \le a_i \le 10^9 \)) liters. All buckets are initially full.

Each minute, the cows pass milk according to a string \( s_1s_2\ldots s_N \) composed only of characters L and R. When cow \( i \) has at least 1 liter of milk, if \( s_i = \texttt{L} \), she passes 1 liter to the cow on her left; if \( s_i = \texttt{R} \), she passes it to the cow on her right. All exchanges happen simultaneously (i.e., if a cow's bucket is full, she gives away 1 liter but also receives 1 liter, so her milk amount remains unchanged). If a cow's milk amount exceeds \( a_i \), the excess milk is lost.

FJ wants to know: after \( M \) minutes (\( 1 \le M \le 10^9 \)), how much milk remains in total for all cows?

Input Format

The first line of input contains \( N \) and \( M \).

The second line contains a string \( s_1s_2\ldots s_N \), consisting only of characters L or R, indicating the direction each cow passes milk.

The third line contains the integers \( a_1, a_2, \ldots, a_N \), representing the capacity of each bucket.

Output Format

Output a single integer, the total amount of milk remaining for all cows after \( M \) minutes.

Note that this problem involves integers that may require 64-bit integer types (e.g., long long in C/C++).

Sample Input and Output

Sample Input #1

3 1
RRL
1 1 1

Sample Output #1

2

Sample Input #2

5 20
LLLLL
3 3 2 3 3

Sample Output #2

14

Sample Input #3

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

Sample Output #3

38

Notes

Explanation for Sample 1

Cows \( 2 \) and \( 3 \) pass 1 liter of milk to each other, so their milk is retained. When cow \( 1 \) passes milk to cow \( 2 \), cow \( 2 \)'s bucket overflows, losing 1 liter of milk after one minute.

Explanation for Sample 2

Each cow passes 1 liter of milk to the cow on her left and receives 1 liter from the cow on her right, so all milk is retained regardless of the time passed.

Explanation for Sample 3

Initially, there are 51 liters of milk. After 5 minutes, cows \( 3 \), \( 6 \), and \( 7 \) will each lose 5, 3, and 5 liters of milk, respectively. Thus, a total of 38 liters of milk remain.

Test Case Properties

• Test cases \( 4-8 \): \( N, M \le 1000 \).
• Test cases \( 9-16 \): No additional restrictions.

见题面 Input 部分

见题面 Output 部分