貪心闖關 (APCS 2025-06 中高級)

小花參加一場搬沙包挑戰賽。賽場上有 \(n\) 個關卡，編號 \(1\) 到 \(n\)，一開始每個關卡上都有一些沙包。

小花搬一次沙包的規則如下：

• 她要挑一個還有沙包的關卡，把那個關卡上的沙包一次全部搬走，不能只搬一部分。
• 她一次最多搬 \(t\) 個沙包，所以只有在那個關卡的沙包數不超過 \(t\) 時才搬得動。搬動 \(w\) 個沙包就得到 \(w\) 分。
• 沙包要搬到編號比它大、而且還有沙包的關卡中編號最小的那一個。搬過去的沙包會跟該關卡原有的沙包堆在一起，以後要搬那一關就得一次搬走合併後的全部沙包。
• 如果她挑的關卡已經是目前還有沙包的關卡中編號最大的，右邊沒有關卡可以接收，就直接把沙包搬出賽場。
• 沙包被搬完的關卡標示為完成，之後不會再有沙包被搬進來。

小花打算照下面的貪心策略進行：

• 每次都選目前沙包最少的關卡；如果有好幾個關卡的沙包一樣少，就選其中編號最小的。
• 重複上面這個步驟，直到挑戰結束。

當所有關卡都完成，或是她選到的關卡沙包數超過 \(t\) 時，挑戰結束——因為她選的是沙包最少的關卡，其他關卡只會更多，一樣搬不動。請算出小花的總分。

輸入格式

第一行有兩個正整數 \(n\) 和 \(t\)，分別代表關卡數，以及小花一次能搬的沙包上限。

第二行有 \(n\) 個正整數，依序代表關卡 \(1\) 到關卡 \(n\) 初始的沙包數。

限制

• \(1\le n\le 3\times10^5\)
• \(1\le t\le10^9\)
• 每個關卡初始的沙包數都是正整數，且不超過 \(10^9\)
• 保證總分不超過 \(10^{15}\)

輸出格式

輸出一個整數，代表小花的總分。如果一開始就沒有任何關卡搬得動，總分為 \(0\)。

評分說明

每筆計分測資各為 5 分，範例不計分。

範例輸入 1

6 8
4 4 2 1 9 3

範例輸出 1

18

範例解釋 1

一開始六個關卡的沙包數是 \((4, 4, 2, 1, 9, 3)\)，一次最多搬 \(8\) 個：

第 3 步選關卡 6 是因為當時沙包最少（\(3\) 個），而且它已經是還有沙包的關卡中編號最大的，所以沙包直接搬出賽場。第 4 步關卡 1 的 \(4\) 個沙包搬到關卡 2，和原有的 \(4\) 個合併成 \(8\) 個。

第 5 步之後只剩關卡 5，上面有 \(20\) 個沙包，超過一次能搬的 \(8\) 個，挑戰結束。總分為 \(1+2+3+4+8=18\)。

範例輸入 2

5 4
4 4 3 2 1

範例輸出 2

10

範例解釋 2

一開始是 \((4, 4, 3, 2, 1)\)，一次最多搬 \(4\) 個：

第 2 步時關卡 5 已經完成，所以關卡 4 是還有沙包的關卡中編號最大的，沙包搬出賽場；第 3 步的關卡 3 同理。

最後只剩關卡 2 的 \(8\) 個沙包，超過上限 \(4\) 個，挑戰結束。總分為 \(1+2+3+4=10\)。

題目來源

APCS 2025 年 6 月實作題第 3 題。

題敘參考 ZeroJudge q838「貪心闖關」 整理，細節可能與正式試題有出入。