题目背景

Facer 是一个爱游泳的孩子。

题目描述

一天他来到了一个 $n \times m$ 的游泳池中，其中第一行是水面，第 $n$ 行是游泳池底。

Facer 想要从 $(1,1)$ 游到 $(1,m)$。他初始速度为 $0$ m/s。

Facer 可以按照以下方式游泳：假设当前 Facer 位于 $(x,y)$，速度为 $v$，那么它可以游到 $(x+v,y+1)$，如果 $x+v>n$，那么就会游到 $(n,y+1)$。

到了每一个格子，Facer 可以选择将自己的速度 $+1$，$-1$ 或者不变，也就是说每次 Facer 有三种选择：

• 游到 $(x+v-1,y+1)$，速度变为 $v-1$。
• 游到 $(x+v,y+1)$，速度变为 $v$。
• 游到 $(x+v+1,y+1)$，速度变为 $v+1$。

游泳池的每个格子上会放有以下两种物品中的一种：

• 变速器，每个变速器有一个属性 $w$，到了这个格子速度会变为 $v+w$（当然原来的 $+1$，$-1$，不变照样存在）。
• 金币盒，每个金币盒中有一定数量的钱 $a$，到了这个位置你可以得到 $a$ 个金币。

除此之外，有以下两点需要注意的：

1. 当 Facer 到达水面，即位于 $(1,x)$ 时，Facer的速度会变成 $0$（当然他仍然可以选择将速度 $+1$，$-1$ 或不变）。
2. Facer 不能在水下待太长时间，相邻两次到水面换气的时间不能超过 $k$ 秒。

求 Facer 能够得到最大金币的数量。

输入格式

第一行三个整数 $n,m,k$。

第二行到第 $n+1$ 行，每行 $m$ 个字符串，表示每个格子物品的情况：

• 首字母为 v，后面接一个整数 $w$，表示该格子中有一个变速器，属性为 $w$。
• 首字母为 s，后面接一个整数 $a$，表示该格子中有一个金币盒，钱数为 $a$。

输出格式

一行一个整数表示答案。

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

提示

数据规模与约定

• 对于 $10\%$ 的数据，$1 \leq n,m \leq 5$。
• 对于 $40\%$ 的数据，$1 \leq n,m \leq 100$。
• 对于 $100\%$ 的数据，$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$。