最接近的子矩陣和 (AP325 Q-2-12)

輸入一個整數二維矩陣 \(A\)（\(M\) 列 \(N\) 行），另外給了一個整數 \(K\)，請計算哪一個子矩陣的和最接近 \(K\) 而不超過 \(K\)；也就是對所有 \(1 \le i \le j \le M\) 與 \(1 \le p \le q \le N\)，在

之中，找出最接近 \(K\) 而不超過 \(K\) 的值。\(M \le 50\) 且 \(M \times N \le 300{,}000\)，每一個整數的絕對值不超過 \(3{,}000\)。

輸入格式

第一行有一個正整數 \(K\)；第二行有兩個正整數 \(M\) 與 \(N\)。接下來，由上而下、從左至右，有 \(M\) 行輸入，每一行有 \(N\) 個整數，代表 \(A[s][t]\)，同行整數間以空格隔開。

限制

• \(1 \le M \le 50\)，\(1 \le N\)，且 \(M \times N \le 300{,}000\)。
• \(1 \le K \le 10^9\)。
• \(|A[s][t]| \le 3{,}000\)。
• 保證至少有一個元素不超過 \(K\)（因此答案一定存在）。

輸出格式

輸出在所有子矩陣和中，最接近 \(K\) 但不超過 \(K\) 的和。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入

6
2 3
-1 -1 1
2 2 2

範例輸出

6

範例說明

取第 \(2\) 列整列，和是 \(2 + 2 + 2 = 6\)，恰好等於 \(K\)。

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 2 章 Q-2-12，第 65 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。原題出自 108 學年度全國高級中等學校資訊學科能力競賽。