58. 探窟專家

探窟專家

今天雷古要開始他的探窟生活，今天要探勘的地方是一個 $H\times W$ 的矩形區域。然而因為雷古非常的膽小，每挖掘每一個地點都有一定的機會挖到祈禱的骸骨，因此雷古偷偷拿來的一張這個區域的危險度測量圖，希望可以找出一個矩形區域，使得區域內 平均 的危險度越小越好。你能根據測量圖幫忙計算最小的平均危險度是多少嗎？

輸入

只有單筆測資。測資第一行有 $2$ 個整數 $H$, $W$ 表示區域的大小。 接下來有 $H$ 行，每行有 $W$ 個數字 $a_{ij}$，表示地圖上每一格的危險程度。

輸出

請輸出最小的危險度如何，如果有小數位，請四捨五入到整數。

條件限制

對於所有測資：

• $1\leq H, W\leq 1000$
• $0\leq a_{ij} \leq 2^{32}-1$

範例輸入1

4 2
2 2
2 2
3 3
4 4

範例輸出1

2

提示

• DP !?

Judge Setting

run-time limit: 1000 ms
memory limit: 1048576 byte
測資數量: 4