# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Perseus and The New Challenge

By farsid.buet · Limits 6s, 512 MB

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.

1. The cave is a 2D grid with n rows and m columns (1 ≤ n ≤ 500, 1 ≤ m ≤ 500).
2. Each cell contains some non-negative integer k or -1. If the value is -1, then the cell is blocked and Perseus cannot go through. Or else Perseus can visit the cell and collect k diamonds from the cell. (0 ≤ k ≤ 109)
3. Perseus can start at any cell in the left border of the grid and travel until he finally stops at a cell in the right border.
4. During this trip, Perseus can only go up/down/right and cannot visit a cell more than once.
5. Even in the left border and right border, Perseus can go up and down.

Special Case:

1. When Perseus is at the top cell of a column, Perseus can still go up by the help of a dragon, which demands him to pay Ci amount of diamond for the ith column, and in return the dragon will teleport Perseus to the bottom cell of the same column and vice versa(i.e. from bottom cell to the top cell). It should be mentioned here that Perseus should have at least Ci amount of diamonds with him to take help of the dragon of ith column. (1 ≤ Ci ≤ 107).

Can you help Perseus to calculate the maximum number of diamonds he can collect?

## Input

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.

## Output

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.

## Sample

InputOutput
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

### Statistics

75% Solution Ratio

triploblasticEarliest, Nov '16

RobbinFastest, 1.9s

RobbinLightest, 3.1 MB

RobbinShortest, 3440B