Hide

Problem D
Dropping Ball

In the second round of the Hunter Exam, the candidates are faced with an even more challenging problem, requiring both agility and mathematical skills.

After entering the Examination Hall for the second round, candidates are faced with a huge vertical grid containing empty spaces, obstacles and conveyor belts. The grid is composed of $K$ identical parts, each of size $(R + 1) \times C$ , stacking vertically on top of each other. In order to pass the exam, each candidate must drop exactly one ball into this grid and get the maximum possible score.

Below is a sample grid with $R = 2$ , $C = 5$ and $K = 2$ :

$\includegraphics[width=0.30\textwidth ]{illustration.jpg}$

Each cell in the grid can be one of the following:

Empty space (colored white in the above image). The ball falls through it.
Obstacle blocking the ball from moving (colored black in the above image). If the ball lands on top of an obstacle, it cannot go anywhere and the exam ends.
Conveyor belt (colored yellow in the above image). All conveyor belts are horizontal and have either left or right direction. Some belts’ direction have been fixed, and you have to set the direction for the others. Based on its direction, a belt sends the ball one unit to the left or to the right. If the ball is sent outside of the grid or to an obstacle, your exam ends immediately.
- In the above grid, ‘R’ and ‘L’ represent a conveyor bell which was already set to right and left, respectively, and ‘?’ represents a conveyor bell which is not yet set.
- Note that two belts in two different parts are considered different. You can set different directions for them, even though they are in the same position in respect to their parts.
Cell with points (colored blue in the above image). A cell belongs to this kind if and only if it is on the last row of some part. This cell contains an integer — the score you gain when the ball lands on this cell. Note that the ball will fall through this square and begins a new part, or if that’s the last part, the exam ends.

As the time for the exam is limited, the exam will also end when the ball goes through $10^{20}$ cells.

Your final score in this exam is the sum of score you get when the exam ends. You don’t have to make the ball fall to the bottom. To pass the exam, you must find a way to set the conveyor belts and set the initial position of the ball to maximize the final score. Can you do it?

Input

The first line of the input contains $3$ integers $R$ , $C$ and $K$ . $(1 \leq R, C \leq 50, 1 \leq K \leq 10^{9})$ .

In the next $R$ line, the $i$ -th line contains exactly $C$ characters. Each character can be one of the following:

‘.’, representing an empty space.
‘X’, representing an obstacle.
‘R’, representing a conveyor belt, which is already set to right.
‘L’, representing a conveyor belt, which is already set to left.
‘?’, representing a conveyor belt, which is not yet set.

The last line of the input contains exactly $C$ integers. The $i$ -th number, $a_{i}$ , represents the score in the $i$ -th column in the last row. $(1 \leq a_{i} \leq 10^{9})$ .

Output

Output contains a single integer — the maximum final score.

Explanation for the first example

We can set the conveyor belt in the first row to ‘R’ and the conveyor belt in the $4$ th row to ‘L’, then drop the ball from the $4$ -th column.

$\includegraphics[width=0.30\textwidth ]{illustration2.jpg}$

Sample Input 1	Sample Output 1
2 5 2 R..?. .X... 100 100 7 100 8	16

Sample Input 2	Sample Output 2
2 3 1 X.. .?. 10 1000 1	10

Sample Input 3	Sample Output 3
2 3 100 X.. .?. 10 1000 1	100

Problem DDropping Ball

Input

Output

Explanation for the first example

Problem D
Dropping Ball