<b>An Animal Contest 3 P7 - Monkey Lasers (Up Version)</b>

<i>Note:</i> This problem is a modified version of <word>this problem</word>. 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, 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 \geq 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 flip the laser's direction. 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\). Moreover, 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?

<b>Constraints</b>

\(\bullet\ 1 \leq N \leq 2 \times 10^5\)

\(\bullet\ 2 \leq M \leq 10^9\)

\(\bullet\ 1 \leq c_i \leq M\)

\(\bullet\ 1 \leq k_i \leq 10^9\)

<b>Input Specification</b>

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 of length \(N\) where the \(i\)-th laser is facing left if \(d_i\) is <word>L</word> and facing right if \(d_i\) is <word>R</word>.

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\).

<b>Output Specification</b>

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

<b>Sample Input 1</b>

\[
2\ 3
1\ 2
LR
7\ 727\ 69
\]

<b>Sample Output 1</b>

\[
11
\]
<b>Subtask 1</b>

We observe that we can maintain a state \((r, c, \text{flip})\). Note that the flip state is simply a boolean.

Now finally, in order to optimize this to \(O(N^2)\) states with an \(O(N)\) transition, we need to observe that there are only \(3N\) relevant columns, those being the ones to the left, on top of, and to the right of the lasers. Proof is left as an exercise to the reader.

This finally yields us a partial solution.

<b>Time Complexity:</b> \(O(N^3)\)

<b>Subtask 2</b>

First, observe that for any \((r, c)\), only one flip state is actually relevant. Since we process row-by-row, we can reject states such that \((r, c, \text{flip})\) would have us vaporized.

Now, we need to optimize our transition.

To do that, note that for each cell, either it is optimal to walk down (flip as needed), or it is optimal to walk just past the laser in the next row. This is simply because it is never optimal to walk farther. If we want to walk farther, we can instead wait until we are on the next row to walk farther.

This allows us to optimize our transition to \(O(1)\).

<b>Time Complexity:</b> \(O(N^2)\)

<b>Subtask 3</b>

For this subtask, we need to optimize both our state and our transition.

To do that, let's throw our state into a segment tree for fun. Now, we want to transition in sub-linear time. To do that, let's break our transition into three parts.

Consider the two lasers, the one in the current row and the one in the next row. Split the sections into left, middle and right. Each section has the same flip state.

Now for all three sections, they can walk down (flipping as needed) into the next row. Alternatively, they can walk to the other side of the laser in the next row.

To do this efficiently, we need a segment tree, make 3 queries, and then 6 updates.

The segment tree needs to support range addition. Also, in order to calculate walk distance for a range and query that, the segment tree should be initialized with the distances from the left and right side. Then we want to query for the minimum \(v + d\) over a range, where \(d\) is the walking distance. Then we need to be able to point update as well.

Implementation details are left as an exercise to the reader. A policy-based implementation is strongly recommended. Specifically, we can write our update and query traversals once, and provide a function to be called at each node, as the "policy". This "Wikipedia" article may be of help.

<b>Time Complexity:</b> \(O(N \log N)\)
solve in c++  using the fastest solution