Annually, from July 27 to August 11, the local carnival opens for business! The main attraction of the carnival this year is a peculiar looking game that you and your friends have decided to try out. The game has layers of wooden boards arranged in a pyramid-like structure (layer has boards), with each board either pointing downwards and to the left or downwards and to the right.
You are told that a ball will be dropped on the topmost board.
There are buckets at the bottom of the structure. Bucket contains dollars worth of coins (because carnivals are a scam, can be negative). You take home all the money in the bucket that the ball eventually lands in.
A ball that lands on the board on the layer, , will fall to the board on the layer if is facing downwards and to the left, or to the board on the layer if is facing downwards and to the right. On the layer, the same rules are applied, however, the ball falls into a bucket on row instead of another board.
Before you drop the ball on the topmost board, you are allowed to flip any board to face downwards and to the left if it was originally facing downwards and to the right, and vice versa. Doing so will cost you dollar. Not wanting to hold up the line, quickly calculate the maximum profit (even if it has to be negative) you can make, and what boards to flip to achieve !
Constraints
Input Specification
The first line contains , the number of levels in the carnival game and the number of buckets.
The next lines represent the layers of the pyramid, with the character on the line representing the orientation of the board on the layer, L
for facing downwards and to the left or R
for facing downwards and to the right.
The final line contains space separated integers .
Output Specification
First, output an integer , the maximum profit you can make.
Next, output an integer , the number of flips made to obtain .
Lastly, output lines each containing two space-separated integers and , representing that the board on the layer was flipped.
Any steps that achieve will be accepted.
Sample Input 1
3
L
RR
-1 0 1
Sample Output 1
0
1
1 1
Explanation for Sample 1
Flipping the first board on the first layer gets us to:
R
RR
We can see that the ball reaches the third bucket in row and we get a profit of dollars. Alternatively, we could flip no boards and have the ball land in the second bucket and make the same profit of dollars.
Sample Input 2
6
L
LL
LLL
LLLL
LLLLL
-727 69 3735 -8210 420 3737
Sample Output 2
3733
2
5 2
4 1
Comments