Description

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.

Input Format

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 Format

Output a single integer, the answer.

3 3 3
s1 v1 s1
s3 s19 v2
v3 s-1 v-1

2

5 10 3
s81 s47 s3 s0 s82 s31 s89 v0 s97 v-1
s14 s94 v1 v-1 v1 s106 v1 v0 v-1 v0
s93 s105 v-1 s219 v0 v0 v-1 v1 s225 v1
v0 s160 v1 v1 s348 s120 s240 s392 s280 s172
s305 s455 s140 v-1 s455 v0 v-1 v0 v1 s410

430

Hint

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