TopCoder

Thumb img 0133
WTF!
我好廢啦晡賴補

User's AC Ratio

100.0% (13/13)

Submission's AC Ratio

87.5% (21/24)

Tags

Description

在某個炎熱的夏天,魔法師覺得好無聊,於是決定去魔法商品店逛逛吹冷氣。來到了魔法商店,店內的門口放了一個小看板,上面寫著:「避暑神器!神奇小毯毯!」。魔法師覺得新奇,就買了一條回家。使用說明書上寫:「小毯毯是由$N \times M$的小格子組成一條$N \times M$的小毯毯,每一塊小格子都有能量值。只要選取小毯毯上的一個矩形區域,小毯毯的溫度便會下降該矩形區域的平均能量值度。」
例如下圖:

若選擇匡起來的矩形部分,小毯毯會下降 (4+5+1+2)/4 度,也就是3度。
請你幫幫魔法師找出小毯毯選一次矩形區域最多能下降幾度。

Input Format

第一行輸入兩個數字$N$ $M$ $( 1 \le N \le 10 ^ 3) $ $ (1\le M \le 10 ^ 3) $
接著輸入$N$ 行 每行有$M$個數字 $a_{ij}$ $( 1 \le a_{ij} \le 10 ^ 5)$
代表小毯毯上每一格的能量值。

Output Format

請輸出小毯毯最多能下降幾度。(若為小數則無條件捨去)

Sample Input

2 3
2 2 1
2 2 1

Sample Output

2

Hints

幫你覺得無聊時,可以下載楓之谷練到10等,去墮落城市找伊卡路斯解「好無聊」這一個任務。

Problem Source

Problem set by Polarz

Subtasks

For Testdata: 0 ~ 4, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536