Shooting Bricks

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.

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.

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