A2138 | Facer爱游泳

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$。

一行一个整数表示答案。