輸入一個整數二維矩陣 \(A[M][N]\)，另外給了一個整數 \(K\)，請計算哪一個子矩陣的和，也就是對所有 \(1 \leq i \leq j \leq M\), \(1 \leq p \leq q \leq N\)，\(\sum_{s=i}^j{\sum_{t=p}^q{A[s][t]}}\) 最接近 \(K\) 而不超過 \(K\)。\(M \leq 50\)且 \(NM \leq 300,000\)，每一個整數的絕對值不超過 \(3,000\)。

輸入格式

每筆測資的第一行有ㄧ個正整數 \(K\)； 第二行有兩個正整數 \(M\) 與 \(N\)。 接下來，由上而下，從左至右，有 \(M\) 行輸入，每一行有 \(N\) 個整數，每一個整數的絕對值不超過 \(3,000\)，代表 \(A[s][t]\)， 同行整數間以空格隔開。

輸出格式

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

範例輸入

6
2 3
-1 -1 1
2 2 2

範例輸出

6