Note: This problem is a modified version of this problem. The only difference is that in this problem, Moses can go up.

Moses the monkey finds himself in a grid with a ton of lasers!

The grid has ~N+2~ rows numbered from ~0~ to ~N+1~, and ~M~ columns numbered from ~1~ to ~M~. Each row ~i~ from row ~1~ to ~N~ has a special laser located on cell ~c_i~ of that row. However, each laser can only face one direction ~d_i~, either left or right, which Moses knows beforehand. A laser located at column ~i~ facing left will vaporize everything in any cell on the same row with column ~j~ where ~j < i~. Similarly, a laser facing right will vaporize every cell on the same row with column ~j > i~.

Moses can start off in any cell on row ~0~. He wishes to reach row ~N+1~, but has a strong desire to not be vaporized. Thus, from his current cell, Moses can move to any adjacent cell inside the grid that does not cause him to be vaporized, incurring a cost of ~1~. If Moses moves into a row where the laser is not looking in his direction, he uses his handy-dandy gadget to destroy it permanently. Note that Moses is not allowed to enter a cell with a laser.

Moses also has a special ability that he can use, and by using his special ability once, he flips the direction of every remaining laser. Using this ability while he is in row ~i~ has a cost of ~k_i~. Note that the special ability is available to be used an infinite number of times in any row between ~0~ and ~N~ inclusive.

Given that Moses can end off in any cell on row ~N+1~, what is the smallest possible cost required to reach row ~N+1~ without being vaporized?

Constraints

~1 \le N \le 2 \times 10^5~

~2 \le M \le 10^9~

~1 \le c_i \le M~

~1 \le k_i \le 10^9~

Input Specification

The first line contains two space-separated integers ~N~ and ~M~.

The next line contains ~N~ space-separated integers ~c_i~, the position of the laser for each row from ~1~ to ~N~.

The third line contains a string ~d~ of length ~N~ where the ~i^{th}~ laser is facing left if ~d_i~ is L and facing right if ~d_i~ is R.

The fourth and final line contains ~N+1~ space-separated integers ~k_i~, the cost of using the special ability on each row from ~0~ to ~N~.

Output Specification

Output one integer representing the minimum cost Moses will incur to reach row ~N+1~.

Sample Input 1

2 3
2 1
LR
7 727 69

Sample Output 1

11

Explanation for Sample 1

For the purposes of this explanation, assume that cell ~(0, 1)~ is the top-leftmost cell and cell ~(N+1, M)~ is the bottom-rightmost cell in the above diagrams. The lasers in each row are labeled with the direction they are facing, L for left and R for right; Moses is represented by the character P.

The diagrams show Moses' situation every time he uses his special ability or makes a move. The following lines describe Moses' journey in chronological order.

The top-left diagram shows the grid's initial state. To minimize cost, Moses decides to start at cell ~(0, 1)~.

The top-middle diagram shows the grid's state after Moses uses his special ability while at row ~0~. This incurs a cost of ~7~.

Moses moves into the grid at cell ~(1, 1)~, incurring a cost of ~1~. He destroys the laser on row ~1~. This is seen in the top-right diagram.

Moses moves right into cell ~(1, 2)~, incurring a cost of ~1~. Since the laser is no longer there, this is a legal move. This is shown in the bottom-left diagram.

Moses then moves down into cell ~(2, 2)~, incurring a cost of ~1~. He destroys the laser on row ~2~. This is depicted by the bottom-middle diagram.

Moses moves down one more time arriving at cell ~(3, 2)~, incurring a cost of ~1~. This is shown by the bottom-right diagram.

Moses has reached row ~N+1~ incurring a total cost of ~11~, which can be proven to be minimal.

Sample Input 2

3 3
1 3 2
LRR
420 563 447 7216

Sample Output 2

5