|
||||||||||
Shooting BricksTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 1418 Accepted Submission(s): 362 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. Sample Input
Sample Output
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! Source | ||||||||||
|