Nông dân John đang tổ chức một sự kiện trao đổi sữa giữa những con bò, trong đó có \(N\) (\(1 \leq N \leq 2 \times 10^5\)) con bò. Mỗi con bò đều mang theo một xô sữa đầy ắp, có sức chứa \(a_i\) (\(1 \leq a_i \leq 10^9\)) lít. Những con bò sau đó xếp thành một vòng tròn và được đánh số thứ tự từ \(1\) đến \(N\) sao cho con bò bên phải con bò \(i\) có số \(i\%N + 1\).

Nông dân John có một xâu hiệu lênh gồm chỉ hai kí tự "R" và "L", trong đó kí tự \(a_i\) là hướng đổ sữa của con bò thứ \(i\). Mỗi phút, những con bò sẽ đồng thời đổ đúng một lít sữa của mình vào xô của con bò bên trái hoặc phải. Nông dân John muốn biết, sau \(M\) (\(1 \leq M \leq 10^9\)) phút, tổng lượng sữa còn lại của đàn bò là bao nhiêu, biết nếu một xô sữa sẽ bị tràn nếu lượng sữa vượt quá sức chứa của nó, và một xô sữa sẽ không thay đổi nếu cho đi và nhận lại sữa cùng một lúc.

Input:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\).
• Dòng thứ hai chứa xâu \(s_1, s_2, \ldots, s_N\) gồm những kí tự "L" và "R" mô tả hướng đổ sữa của những con bò
• Dòng thứ ba chứa \(N\) số nguyên \(a_1, a_2, \ldots, a_N\) mô tả dung tích của những cái xô

Output:

• Gồm một số nguyên duy nhất là tổng lượng sữa còn lại sau \(M\) phút.

Scoring

• Subtask 1: \(N,M \leq 1000\)
• Subtask 2: Không có ràng buộc gì thêm.

Example:

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

34