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 rows numbered from to , and columns numbered from to . Each row from row to has a special laser located on cell of that row. However, each laser can only face one direction , either left or right, which Moses knows beforehand. A laser located at column facing left will vaporize everything in any cell on the same row with column where . Similarly, a laser facing right will vaporize every cell on the same row with column .
Moses can start off in any cell on row . He wishes to reach row , 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 . 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 has a cost of . Note that the special ability is available to be used an infinite number of times in any row between and inclusive.
Given that Moses can end off in any cell on row , what is the smallest possible cost required to reach row without being vaporized?
The first line contains two space-separated integers and .
The next line contains space-separated integers , the position of the laser for each row from to .
The third line contains a string of length where the laser is facing left if is
L and facing right if is
The fourth and final line contains space-separated integers , the cost of using the special ability on each row from to .
Output one integer representing the minimum cost Moses will incur to reach row .
Sample Input 1
2 3 2 1 LR 7 727 69
Sample Output 1
Explanation for Sample 1
For the purposes of this explanation, assume that cell is the top-leftmost cell and cell 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
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 .
The top-middle diagram shows the grid's state after Moses uses his special ability while at row . This incurs a cost of .
Moses moves into the grid at cell , incurring a cost of . He destroys the laser on row . This is seen in the top-right diagram.
Moses moves right into cell , incurring a cost of . 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 , incurring a cost of . He destroys the laser on row . This is depicted by the bottom-middle diagram.
Moses moves down one more time arriving at cell , incurring a cost of . This is shown by the bottom-right diagram.
Moses has reached row incurring a total cost of , which can be proven to be minimal.
Sample Input 2
3 3 1 3 2 LRR 420 563 447 7216
Sample Output 2