先到先服務 (AP325 Q-4-8)

有 \(n\) 個客人要分配到 \(m\) 個櫃台來服務，客人依編號順序到達，第 \(i\) 個客人需要 \(t(i)\) 的時間來完成（無論分配到哪一個櫃台），而且每個客人的需求必須在同一個櫃台完成。因為公平的因素，先到客人不可以比晚到客人更晚開始服務。現在希望安排每個客人的服務櫃台，以便可以在最短的時間內完成所有客人的需求。

舉例來說，如果有三位客人與兩個櫃台，需求的時間依序是 \((3, 1, 5)\)，我們可以如下圖分配，最後的完成時間是 \(6\)。

請注意，我們不可以如下分配，雖然這樣的完成時間會減少到 \(5\)，但是第 \(3\) 個客人比第 \(2\) 個客人早開始服務違反了先到先服務的原則。

輸入格式

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

限制

• \(1 \le n \le 2 \times 10^5\)，\(1 \le m \le 2 \times 10^5\)。
• \(1 \le t(i) \le 10^4\)。

輸出格式

輸出最早可能服務完所有客人的時間。

評分說明

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

範例輸入

3 2
3 1 5

範例輸出

6

題目來源

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