Description

Xiaohong really likes to play a game called Brick Breaker. The rules are as follows:

At the beginning, there are $n$ rows and $m$ columns of bricks, and Xiaohong has $k$ bullets. Each time, she can spend one bullet to break the brick that is currently at the bottom of some chosen column, and gain the corresponding score (as shown in the figure).

Some bricks, after being broken, may also award one bonus bullet. The game ends when all bricks are broken or when Xiaohong has no bullets left.

Before the game starts, Xiaohong already knows the score obtained by breaking each brick and whether it awards a bonus bullet. She wants to know the maximum possible total score she can achieve in this game, but this problem is too difficult for her. Can you help her?

Input Format

The first line contains 3 positive integers, $n,m,k$. They indicate that initially there are $n$ rows and $m$ columns of bricks, and Xiaohong has $k$ bullets.

Next there are $n$ lines, each in the following format:
$f_1~c_1~f_2~c_2~f_3~c_3\cdots f_m~c_m$

Here $f_i$ is a positive integer, denoting the score of the brick in row $i$ and the chosen column after it is broken. $c_i$ is a character with only two possibilities, Y or N. Y indicates a bonus bullet is awarded, and N indicates none.

All numbers and characters are separated by a single space, and there are no extra spaces at the end of a line.

Output Format

Output a single positive integer, the maximum total score.

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

Hint

For 20% of testdata, $1 \le n,m \le 5$, $1 \le k \le 10$, and all characters $c$ are N.

For 50% of testdata, $1 \le n,m \le 200$, $1 \le k \le 200$, and all characters $c$ are N.

For 100% of testdata, $1 \le n,m \le 200$, $1 \le k \le 200$, and characters $c$ may be Y.

For 100% of testdata, all $f$ satisfy $1 \le f \le 10000$.

Translated by ChatGPT 5