少林寺的櫃姐 (AP325 Q-4-18)

少林寺是觀光勝地，每天要接待很多客人，根據數據分析，方丈決定即使在尖峰時期也必須在時間 \(D\) 內完成 \(n\) 個客人的服務，現在的問題是不知道要開設多少個服務櫃台。假設客人依編號順序到達，第 \(i\) 個客人需要 \(t(i)\) 的時間來完成他的需求（無論分配到哪一個櫃台），而且每個客人的需求必須在同一個櫃台完成。因為公平的因素，先到客人的服務開始時間不可以大於晚到客人的服務開始時間。因為每開設一個櫃台就要請一位櫃姐，為了節省人事成本，請計算出最少要開設多少櫃台才能讓這 \(n\) 個客人的服務都在時間 \(D\) 內完成。

服務從時間 \(0\) 開始，每個櫃台一次只服務一位客人；一位客人的服務一旦開始就不會中斷，直到花完 \(t(i)\) 的時間。

輸入格式

輸入兩行，第一行是正整數 \(n\) 與 \(D\)，第二行是 \(n\) 個正整數 \(t(1), t(2), \ldots, t(n)\)，同行數字間以空白間隔。

限制

• \(1 \le n \le 10^5\)。
• \(1 \le t(i) \le 10^4\)。
• \(D \le 10^9\)，且 \(D\) 不小於任何一個 \(t(i)\)，所以一定有解。

輸出格式

輸出最少的櫃台數。

評分說明

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

範例輸入

5 9
3 2 5 7 3

範例輸出

3

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 4 章 Q-4-18，第 141 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。