Circling Cows Milk Passing

Farmer John has N cows arranged in a circle. For every cow i (1 ≤ i ≤ N) the cow on its right is cow i+1 (with cow N’s right neighbor being cow 1). The i-th cow has a bucket of capacity a_i liters (1 ≤ a_i ≤ 10⁹). Initially every bucket is full (containing exactly a_i liters).

Every minute, the cows pass milk simultaneously according to a given string s = s₁s₂…s_N, where each character is either L or R. At the start of a minute, if cow i has at least 1 liter, then:

• If si = R, cow i sends 1 liter to her right neighbor (cow i+1, with cow N sending to cow 1).
• If si = L, she sends 1 liter to her left neighbor (cow i-1, with cow 1 sending to cow N).

All the milk transfers occur simultaneously. (Thus, even if a cow sends out 1 liter because her bucket is full and simultaneously receives 1 liter from a neighbor, her milk quantity remains the same.) After transfers, if a cow’s milk quantity exceeds her bucket capacity, the extra milk is lost.

Farmer John wants to know the total amount of milk remaining in all the cows after M minutes (1 ≤ M ≤ 10⁹).

Important observation: When a cow passes milk, its net change is given by:

$$x_i \to \min\Bigl(a_i,\; x_i - 1 + \bigl(\mathbf{1}_{\{s_{i-1}=R\}}+\mathbf{1}_{\{s_{i+1}=L\}}\bigr)\Bigr), $$

where indices are taken modulo N (with cow 0 being cow N and cow N+1 being cow 1). Initially all cows have exactly a_i liters. It turns out that due to the simultaneous transfers, a cow will remain full (i.e. its bucket contains a_i liters) forever provided that at least one of its two neighbors continuously sends milk to her. In our setting the only way a cow i loses milk is if both potential incoming directions fail. In fact, one may prove that cow i eventually loses milk if and only if

$$s_{i-1}=L \quad\text{and}\quad s_{i+1}=R.$$

For such a cow, no neighbor is permanently supplying milk, and hence after each minute her bucket loses 1 liter. Consequently, after M minutes her milk will be max(ai - M, 0).

Thus, the final answer is the sum over all cows, where if cow i has

$$s_{i-1}=L \quad\text{and}\quad s_{i+1}=R,$$

its milk becomes max(ai - M, 0), and otherwise it remains at a_i liters.

inputFormat

The first line contains two integers N and M — the number of cows and the number of minutes.

The next line contains N integers a₁, a₂, …, a_N — the capacities (in liters) of the buckets.

The last line contains a string s of length N consisting only of the characters L and R.

outputFormat

Output a single integer, the total amount of milk remaining in all cows after M minutes.

sample

3 3
3 5 2
LLR

8

</p>