TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

33.3% (2/6)

Tags

Description

探險家千里在走了上百里的路途後,終於找到了傳說中埋藏寶藏的遺跡,為了走入遺跡,找到寶藏,千里必須破解層層關卡:
每一道關卡都有一枚主教棋以及一張有大小為 $n\times m$ 的魔法棋盤,魔法棋盤上的每個格子都有一個正整數,代表該格子的魔力值,根據石碑上的說明,千里必須將主教放在棋盤上的某個方格,使得主教攻擊範圍內的總魔力值最大化才可以破解關卡,主教的攻擊範圍是對角線上的所有位置,特別注意放置主教的那個格子也算在主教的攻擊範圍內。危險的是,如果千里放錯的話就會被夜光閃亮亮復仇鬼吃掉。
身為一個路過的好心人,你決定告訴千里魔力值總和的最大值作為提示。
以下是主教的攻擊範圍的圖示:



Input Format

第一行包含一個正整數 $t\ (1\le t\le 1000)$ 代表測資的數量。
每一筆測資的第一行包含兩個正整數 $n, m\ (1\le n, m\le 200)$ 代表棋盤的大小。
接下來的 $n$ 行,每一行都包含 $m$ 個數字,分別是方格棋盤由上而下,由左而右的魔力值,魔力值皆為不超過 $10^ 6$ 的非負整數,同一行的數字之間以空白分隔。
此外,所有測資的 $n\times m$ 的總和不會超過 $40000$

Output Format

對於每一筆測資請輸出一個整數,代表該筆測資中,主教攻擊範圍內的魔力值總和的最大值,每筆測資的輸出之間以換行分隔。

Sample Input 1

4
4 4
1 2 2 1
2 4 2 4
2 2 3 1
2 4 2 4
2 1
1
0
3 3
1 1 1
1 1 1
1 1 1
3 3
0 1 1
1 0 1
1 1 0

Sample Output 1

20
1
5
3

Hints

Problem Source

Codeforces 1676D

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~12 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2