Problem Description

Kris has a deep affection for a computer game named Shooting Bricks, described as follows:

The game is initialized with $n\times m$ bricks, placed in $n$ rows and $m$ columns. Players will be able to choose a column and shoot the outermost brick with a pistol. Shooting different bricks results in different bonus points, and shot bricks will disintegrate into ashes. Moreover, by shooting some special bricks, players can get a single bullet as a reward. It is the players' goal to achieve the highest overall bonus score.

Now Kris only has $k$ bullets, and he wonders how many bonus points he can obtain at most.

Input

This problem contains multiple test cases.

The first line contains an integer $T(1\le T\le 20)$, the number of test cases.

Each test case starts with a line of three integers $n,m,k(1\le n,m,k\le 200)$.

Then $n$ lines follow. The $i$th line contains $m$ pairs of $f_{ij},c_{ij}(1\le f_{ij}\le 10^4,c_{ij}\in \{\texttt{Y},\texttt{N}\})$, meaning if the brick located at the $i$th line and $j$th column is shot, player will get $f_{ij}$ points and will(Y) or won't(N) get a reward bullet after that. Initally, the bricks at the $n$th line is exposed outside, so you need to shoot them as a start.

Output

For each test case, print a line of a single integer, denoting the highest bonus score.

1
2 2 1
1 Y 1 N
1 Y 1 Y

4

Hint

In the example, all bricks can be shot, shooting sequence (2, 1), (1, 1), (2, 2), (1, 2) is one of the solutions.

Here is a link that may help you understand this problem. But please notice that it has nothing to do with this problem.

https://ccpc-online-2021.github.io/brick

Pay attention to the time you waste!