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

輸入格式

輸入兩行，第一行是正整數 \( n \) 與 \( m\) ， 第二行是 \( n \) 個正整數 \( t(1),t(2),…,t(n)\) ， 同行數字間以空白間格。 \(n \) 與 \( m \) 不超過 \( 2e5，t(i)\) 不超過 \( 1e4\) 。

輸出格式

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

範例輸入

3 2
3 1 5

範例輸出

6