Siruseri政府決定將石油資源豐富的Navalur省的土地拍賣給私人承包商以建立油井。被拍賣的整塊土地為一個矩形區(qū)域，被劃分為M×N個小塊。
Siruseri地質調(diào)查局有關于Navalur土地石油儲量的估測數(shù)據(jù)。這些數(shù)據(jù)表示為M×N個非負整數(shù)，即對每一小塊土地石油儲量的估計值。
為了避免出現(xiàn)壟斷，政府規(guī)定每一個承包商只能承包一個由K×K塊相連的土地構成的正方形區(qū)域。
AoE石油聯(lián)合公司由三個承包商組成，他們想選擇三塊互不相交的K×K的區(qū)域使得總的收益最大。
例如，假設石油儲量的估計值如下：
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 1 1 1 8 8 8 1 1
1 1 1 1 1 1 8 8 8
1 1 1 1 1 1 9 9 9
1 1 1 1 1 1 9 9 9

如果K  =  2,  AoE公司可以承包的區(qū)域的石油儲量總和為100,  如果K  =  3,  AoE公司可以承包的區(qū)域的石油儲量總和為208。
AoE公司雇傭你來寫一個程序，幫助計算出他們可以承包的區(qū)域的石油儲量之和的最大值。

輸入第一行包含三個整數(shù)M,  N,  K，其中M和N是矩形區(qū)域的行數(shù)和列數(shù)，K是每一個承包商承包的正方形的大?。ㄟ呴L的塊數(shù)）。接下來M行，每行有N個非負整數(shù)表示這一行每一小塊土地的石油儲量的估計值。 

數(shù)據(jù)規(guī)模和約定
數(shù)據(jù)保證K≤M且K≤N并且至少有三個K×K的互不相交的正方形區(qū)域。M,  N≤  1500。每一小塊土地的石油儲量的估計值是非負整數(shù)且≤  500。

零基礎同學可以先學習視頻課程，包含C/C++、Python、百練、藍橋杯輔導、算法數(shù)據(jù)結構等課程，提供視頻講解以及配套習題，還有老師答疑，點擊這里了解課程詳情

藍橋杯