A21225.Facer爱游泳
提高+/省选-
通过率：0%
时间限制：1.00s
内存限制：128MB
题目描述
Facer 是一个爱游泳的孩子。一天他来到了一个 n×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 个金币。
除此之外，有以下两点需要注意的：
- 当 Facer 到达水面，即位于 (1,x) 时，Facer的速度会变成 0（当然他仍然可以选择将速度 +1，−1 或不变）。
- Facer 不能在水下待太长时间，相邻两次到水面换气的时间不能超过 k 秒。
求 Facer 能够得到最大金币的数量。
输入格式
第一行三个整数 n,m,k。
第二行到第 n+1 行，每行 m 个字符串，表示每个格子物品的情况：
- 首字母为
v，后面接一个整数 w，表示该格子中有一个变速器，属性为 w。 - 首字母为
s，后面接一个整数 a，表示该格子中有一个金币盒，钱数为 a。
输出格式
一行一个整数表示答案。
输入输出样例
输入#1
3 3 3 s1 v1 s1 s3 s19 v2 v3 s-1 v-1
输出#1
2
输入#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
输出#2
430
说明/提示
1≤n≤100，1≤m≤1000，1≤k≤10，−20≤w≤20，−1000≤a≤1000。