a306. TOI 2021/03 潛力組：農地

題目描述

一塊土地分成 N × N 個單位格。每格記錄開墾成本，其中 −1 表示不能砍除的大樹，不能納入開墾範圍。

你要選擇一個邊界沿著格線的正方形區域開墾。區域內不得有大樹，且所有格子的成本總和不能超過預算 U。請求出可以開墾的最大面積，也就是所選區域的格子數。

輸入格式

第一行有 N、U。接著 N 行，每行 N 個整數 a，依序表示各格狀況。

• 1 ≤ N ≤ 3000
• 1 ≤ U ≤ 1000000000
• −1 ≤ a ≤ 100；a = −1 表示大樹，其餘數值為成本。

輸出格式

輸出最大可開墾面積。若連一格都無法選擇，輸出 0。

來源

TOI 2021 年 3 月潛力組〈農地〉。依官方題目之 ZeroJudge f737 鏡像重述；範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202103/Farmland.pdf