황금 모으기

프리기아에서는 길이 황금으로 포장되어 있다는 말이 있습니다. 마침 프리기아로 여행을 온 당신은 이 말이 문자 그대로 사실임을 알게 됩니다. 도시 곳곳에 작은 황금 더미가 흩어져 있습니다. 어느 특별한 날에는 관광객들이 정해진 직사각형 구역 안에서 원하는 만큼 황금을 주워 갈 수 있도록 허락됩니다. 그날이 바로 내일이고, 당신은 이 기회에 큰 부자가 되기로 마음먹었습니다. 하지만 다른 관광객들도 모두 같은 생각을 했기 때문에 구역은 매우 붐빌 것입니다. 그래서 이 구역을 단 한 번만 가로지를 수 있습니다. 어떻게 지나가야 가장 많은 황금을 모을 수 있을까요?

직사각형 지도와 각 칸에 놓인 황금의 양이 주어집니다. 지도의 왼쪽 위 칸에서 출발하여 매 단계마다 동쪽, 남쪽, 또는 남동쪽으로 인접한 칸으로 이동해 오른쪽 아래 칸에 도착할 때, 모을 수 있는 황금의 최대량을 구하세요.

첫 줄에 테스트 케이스의 개수를 나타내는 정수 하나가 주어집니다.

각 테스트 케이스의 첫 줄에는 두 정수 $r$과 $c$가 공백으로 구분되어 주어집니다 ($1 \le r, c \le 1000$). 이어서 $r$개의 줄이 주어지며, 각 줄에는 $c$개의 정수가 공백으로 구분되어 주어집니다. 이 정수들은 각 칸에 놓인 황금의 양을 나타냅니다. 황금의 양은 음수가 아닙니다.

모을 수 있는 황금의 최대량은 항상 int 범위 안에 들어갑니다.

각 테스트 케이스마다 먼저 Scenario #i: 형식의 줄을 출력합니다. 여기서 $i$는 테스트 케이스의 번호입니다. 그다음 줄에 해당 테스트 케이스에서 모을 수 있는 황금의 최대량을 출력합니다. 연속한 두 테스트 케이스 사이는 빈 줄 하나로 구분하며, 마지막 테스트 케이스 뒤에는 빈 줄을 출력하지 않습니다.