The life of princess Andromeda, the daughter of King Cepheus and Queen Cassiopeia of Ados, is in danger as she is captive inside the cave of the most atrocious monster of all time, the Kraken. Killing the Kraken is beyond the reach of any human. But the Ephors of the kingdom has finally discovered a way to weaken the Kraken. In some parts of the cave of Kraken is hidden some special kind of diamonds. If someone can collect the diamonds from the cave, then the Kraken can be sent into deep slumber with some magic spells. The higher the number of diamonds, the stronger the spell would be.
But the task is perilous. Nobody in the kingdom is brave enough to go to the cave. Finally, Perseus, the famous Greek hero comes to the rescue. The Ephors introduce the rules of collecting the diamonds to Perseus.
Special Case:
Can you help Perseus to calculate the maximum number of diamonds he can collect?
Input starts with an integer T (T ≤ 150), denoting the number of test cases. Each case starts with a blank line. The next line contains two positive integers n and m. Each of the next n lines contains m integers k that fill up the grid (if k is -1, then the cell is blocked). The next line contains m space separated integers Ci denoting the cost the dragon would be demanding to teleport him from the top to the bottom or from the bottom to the top of the ith column. Each case is separated by a blank line.
For each case, output the case number followed by the maximum number of diamond Perseus can collect. If it is impossible to move to the rightmost column as described, print 'Trapped' instead of the number.
Please refer to the sample input output for correct formatting.
Input | Output |
---|---|
4 4 4 -1 4 5 1 2 -1 2 4 3 3 -1 -1 4 2 1 2 50 11 17 50 4 4 -1 4 5 1 2 -1 2 4 3 3 -1 -1 4 2 1 2 50 13 17 50 4 4 -1 4 5 1 2 -1 2 4 3 3 -1 -1 4 -1 1 2 50 7 17 50 4 4 -1 4 5 1 2 -1 2 4 3 3 -1 3 4 2 1 2 50 50 50 50 | Case 1: 17 Case 2: 15 Case 3: Trapped Case 4: 23 |