Problem Background

Facer is a child who loves swimming.

Problem Description

One day, he arrives at a swimming pool of size $n \times m$, 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 in the following manner: Suppose he is currently at $(x,y)$ with speed $v$. He can then swim to $(x+v,y+1)$. If $x+v > n$, he will swim to $(n,y+1)$.

At each grid, Facer can choose to increase, decrease, or maintain his speed. This means he has three options:

• Swim to $(x+v-1,y+1)$ with speed $v-1$.
• Swim to $(x+v,y+1)$ with speed $v$.
• Swim to $(x+v+1,y+1)$ with speed $v+1$.

Each grid in the swimming pool contains one of the following items:

• A speed changer with an attribute $w$. Upon reaching this grid, his speed becomes $v+w$ (while the options to increase, decrease, or maintain speed still apply).
• A coin box containing a certain amount of money $a$. Upon reaching this grid, he can collect $a$ coins.

Additionally, there are two important points to note:

1. When Facer reaches the water surface, i.e., at $(1,x)$, his speed becomes $0$ (though he can still choose to increase, decrease, or maintain his speed).
2. Facer cannot stay underwater for too long; the time between two consecutive surface breaths cannot exceed $k$ seconds.

Determine the maximum number of coins Facer can collect.

Input Format

The first line contains three integers $n, m, k$.

The next $n$ lines, each containing $m$ strings, describe the items on each grid:

• A string starting with v followed by an integer $w$ indicates a speed changer with attribute $w$.
• A string starting with s followed by an integer $a$ indicates a coin box with $a$ coins.

Output Format

A single integer representing the answer.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2

Sample Input #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

Sample Output #2

430

Notes

Data Size and Constraints

• For $10\%$ of the data, $1 \leq n, m \leq 5$.
• For $40\%$ of the data, $1 \leq n, m \leq 100$.
• For $100\%$ of the data, $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$.

见题面 Input 部分

见题面 Output 部分