luogu#P1174. 打砖块

打砖块

题目描述

小红很喜欢玩一个叫打砖块的游戏,这个游戏的规则如下:

在刚开始的时候,有 nnmm 列的砖块,小红有 kk 发子弹。小红每次可以用一发子弹,打碎某一列当前处于这一列最下面的那块砖,并且得到相应的得分。(如图所示)

某些砖块在打碎以后,还可能将得到一发子弹的奖励。最后当所有的砖块都打碎了,或者小红没有子弹了,游戏结束。

小红在游戏开始之前,就已经知道每一块砖在打碎以后的得分,并且知道能不能得到一发奖励的子弹。小红想知道在这次游戏中她可能的最大得分,可是这个问题对于她来说太难了,你能帮帮她吗?

输入格式

第一行有 33 个正整数,n,m,kn,m,k。表示开始的时候,有 nnmm 列的砖块,小红有 kk 发子弹。

接下来有 nn 行,每行的格式如下:

f1 c1 f2 c2 f3 c3fm cmf_1~c_1~f_2~c_2~f_3~c_3\cdots f_m~c_m

其中 fif_i 为正整数,表示这一行的第 ii 列的砖,在打碎以后的得分。cic_i 为一个字符,只有两种可能,Y 或者 NY 表示有一发奖励的子弹,N 表示没有。

所有的数与字符之间用一个空格隔开,行末没有多余的空格。

输出格式

仅一个正整数,表示最大的得分。

3 4 2
9 N 5 N 1 N 8 N
5 N 5 Y 5 N 5 N
6 N 2 N 4 N 3 N
13

提示

对于 20%20\% 的数据,满足 1n,m51 \le n,m \le 51k101 \le k \le 10,所有的字符 cc 都为 N

对于 50%50\% 的数据,满足 1n,m2001 \le n,m \le 2001k2001 \le k \le 200,所有的字符 cc 都为 N

对于 100%100\% 的数据,满足 1n,m2001 \le n,m \le 2001k2001 \le k \le 200,字符 cc 可能为 Y

对于 100%100\% 的数据,所有的 ff 值满足 1f100001 \le f \le 10000