Swimming Pool Challenge

Facer is in a swimming pool of size \(n \times m\) where the first row \((1,\cdot)\) is the water surface and the \(n\)th row is the pool bottom. Facer starts at \((1,1)\) with an initial speed of \(0\) m/s and wants to reach \((1,m)\) (i.e. the water surface at column \(m\)).

In each move, if Facer is at \((x,y)\) with speed \(v\), he can choose one of three actions by adjusting his speed by \(-1\), \(0\), or \(+1\). That is, if he chooses an adjustment \(\delta\in\{-1,0,1\}\), he will move to cell \((x+v+\delta,y+1)\). Note that if \(x+v+\delta>n\), he will be clamped to row \(n\), and if \(x+v+\delta<1\) he is clamped to row \(1\) (the water surface).

After arriving at the new cell, the following occurs in order:

1. If the cell contains an accelerator with parameter \(w\), Facer's speed is updated to \(v+\delta+w\). If instead the cell contains a coin box with value \(a\), Facer collects \(a\) coins and his speed remains \(v+\delta\).
2. If the cell is on the water surface (i.e. its row is \(1\)), then Facer's speed is reset to \(0\). Otherwise, Facer is underwater and his air supply is limited: the number of moves between consecutive visits to the water surface cannot exceed \(k\). In other words, if he has been underwater for more than \(k\) consecutive moves, that path is invalid.

Compute the maximum number of coins Facer can collect while reaching the water surface at \((1,m)\).

The input follows the format described below.

inputFormat

The first line contains three integers \(n\), \(m\), and \(k\) \( (1\le n,m\le \text{small},\, k\ge 1)\), where \(n\) is the number of rows and \(m\) is the number of columns of the swimming pool, and \(k\) is the maximum allowed underwater moves between visits to the water surface.

Then follow \(n\) lines, each containing \(m\) tokens separated by spaces. Each token is in one of the following formats:

• Aw: indicating an accelerator with integer parameter \(w\) (which can be negative, zero, or positive).
• Ca: indicating a coin box containing \(a\) coins (\(a\) is an integer).

Note that the grid is given row by row, with the first row corresponding to the water surface and the \(n\)th row to the pool bottom.

outputFormat

Output a single integer, the maximum number of coins Facer can collect while reaching \((1,m)\) (the water surface at column \(m\)). If it is impossible to reach \((1,m)\) under the given constraints, output an appropriate value (for these test cases, you may assume a solution always exists).

sample

3 3 1
C0 C0 C0
A1 C2 A-1
C1 C0 C1

0