一天他来到了一个 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 个金币。

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

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

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

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

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

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

一行一个整数表示答案。

数据规模与约定

• 对于 10% 的数据，1≤n,m≤5。
• 对于 40% 的数据，1≤n,m≤100。
• 对于 100% 的数据，1≤n≤100，1≤m≤1000，1≤k≤10，−20≤w≤20，−1000≤a≤1000。