Filthy Rich

They say that in Phrygia the streets are paved with gold. You are on vacation in Phrygia, and to your astonishment you discover that this is meant literally: small heaps of gold are scattered throughout the city. On one special day, the Phrygians even allow every tourist to collect as much gold as they can within a fixed rectangular area. That day happens to be tomorrow, and you decide to become filthy rich. Every other tourist made the same decision, though, so the area will be crowded, and you only get one chance to cross it. What is the best way to do so?

You are given a rectangular map together with the amount of gold on every cell. Starting from the upper-left cell of the map and moving, at each step, to an adjacent cell to the east, south, or south-east until you reach the lower-right cell, determine the maximum amount of gold you can collect.

The first line contains a single integer: the number of test cases.

Each test case begins with a line containing two integers $r$ and $c$, separated by a space ($1 \le r, c \le 1000$). This line is followed by $r$ rows, each containing $c$ integers separated by spaces. These integers give the amount of gold on each cell. The amount of gold is never negative.

The maximum amount of gold always fits in an int.

For each test case, first print a line of the form Scenario #i:, where $i$ is the number of the test case. On the next line, print the maximum amount of gold you can collect in this test case. Separate consecutive test cases with a single blank line; do not print a blank line after the last test case.