為了慶祝你終於在 APCS 測驗中拿下實作題滿分的佳績，你決定買一個大蛋糕來與眾人分享你的喜悅。

大蛋糕由 $N$ 行 $M$ 列的正方體小蛋糕拼湊而成，對於其第 $i$ 行第 $j$ 列的小蛋糕，你認為他的好吃程度為 $d_{i,j}$。在切蛋糕時，為了不破壞蛋糕的美觀，你會選擇相鄰兩列或相鄰兩行小蛋糕之間的交界處，並將完整的整行或整列切開。

舉例來說，下圖以紅線表示切蛋糕的位置。左側的兩張圖是合法的切蛋糕方式，但最右側的圖不是。

在切完蛋糕後，你會將每一塊蛋糕裝在一個盤子上，好分送給其他人。你想要最大化每一塊蛋糕從外側能看到的部分的好吃程度的總和。也就是說，每一塊切下來的蛋糕都有正上方及前、後、左、右五個看得到的面，你想將所有切塊的蛋糕的這些好吃程度相加，並最大化這個值。

舉例來說，下圖方格上的數字表示其好吃程度。若依紅線方式切大蛋糕，並將左上角的蛋糕裝在盤子上後，其外觀分別如下。這塊蛋糕的好吃程度總和為 $21+10+11+6+8=56$。而另外三塊蛋糕的好吃程度總和分別為 $52,37,50$，故以這種方式切蛋糕你可以得到的外側的好吃程度總和為 $56+52+37+50=195$。

因為你還不知道會有多少人要來一起分享，你想知道對於每一個介於 $[1,N\times M]$ 的正整數 $K$，切出恰好 $K$ 塊蛋糕的好吃程度總和最大可以是多少，或是判斷不存在合法的方式切出恰好 $K$ 塊蛋糕。相信這樣的問題對已經在 APCS 實作題拿下滿分的你來說一定是一塊小蛋糕。