P2795 Facer Loves Swimming

Facer is a child who loves swimming.

One day he came to an $n \times m$ swimming pool, where the first row is the water surface and the $n$-th row is the bottom of the pool.  Facer wants to swim from $(1, 1)$ to $(1, m)$. His initial speed is $0$ m/s. Facer can swim as follows: suppose Facer is currently at $(x, y)$ with speed $v$, then he can swim to $(x+v, y+1)$. If $x+v > n$, he will instead swim to $(n, y+1)$. Upon reaching each cell, Facer can choose to change his speed by $+1$, $-1$, or keep it unchanged. That is, each time Facer has three choices: - Swim to $(x+v-1, y+1)$ and the speed becomes $v-1$. - Swim to $(x+v, y+1)$ and the speed becomes $v$. - Swim to $(x+v+1, y+1)$ and the speed becomes $v+1$. Each cell in the swimming pool contains exactly one of the following two items: - Accelerator: each accelerator has an attribute $w$. Upon reaching this cell, the speed becomes $v+w$ (of course, the original options of $+1$, $-1$, or unchanged still apply). - Coin box: each coin box contains an amount $a$. Upon reaching this cell, you obtain $a$ coins. In addition, note the following: 1. When Facer reaches the surface, i.e., is at $(1, x)$, Facer’s speed becomes $0$ (he can still choose to change his speed by $+1$, $-1$, or keep it unchanged). 2. Facer cannot stay underwater for too long. The time between two consecutive surfacings cannot exceed $k$ seconds. Find the maximum number of coins Facer can obtain.

The first line contains three integers $n, m, k$. From the second line to line $n+1$, each line contains $m$ strings describing the item in each cell: - If the first character is ```v``` followed by an integer $w$, then the cell contains an accelerator with attribute $w$. - If the first character is ```s``` followed by an integer $a$, then the cell contains a coin box with amount $a$.

Output a single integer, the answer.

Constraints - For $10\%$ of the testdata, $1 \leq n, m \leq 5$. - For $40\%$ of the testdata, $1 \leq n, m \leq 100$. - For $100\%$ of the testdata, $1 \leq n \leq 100$, $1 \leq m \leq 1000$, $1 \leq k \leq 10$, $-20 \leq w \leq 20$, $-1000 \leq a \leq 1000$. Translated by ChatGPT 5