# 衝擊台大書卷獎

## Description

**極速車神大佬**即將進入**台灣大學資訊工程學系**就讀。為了獲得書卷獎，他安排了一連串共$N$個的讀書計畫，每個計畫需要花費$a_i$天的時間來完成。

當然，在台大資工裡可不是單純地努力念書就能獲得書卷獎的，畢竟裡面那麼多怪物。而**極速車神大佬**獲得書卷獎的關鍵，就在於他有**一心多用**的能力。

他能夠把腦力分成$M$部分，同時進行$M$個讀書計畫。不過這個能力有個限制，因為讀書計畫有連續性，所以她每部分的腦力只能處理一段連續的讀書計畫。

舉例來講，有5個讀書計畫，他一部份的腦力不能處理第1、3、5個，因為它不連續，但可以處理第2、3、4個。

請問，如果他想在最短時間內完成這個讀書計畫，須要花多久的時間

(所花時間為每部分腦力處理的任務中，耗時最久的)

## Input

第一行包括兩個數字$N$,$M$，$N$代表讀書計畫的數量，$M$代表腦力可以分成的數量，也就是一心可以多少用。

第二行包括$N$個數字$a\_i$，$a\_i$代表第$i$項任務。

測資範圍:

$1<=N<=5*10^7$

$1<=M<=10^5$

$1<=a_i<=10^9$

## Output

請輸出最短的花費時間  

## Sample Input 1

9 3
1 2 3 4 5 6 7 8 9

## Sample Input 2

9 3
13 24 27 19 11 21 29 15 8

## Hint

範例測資1中，可以做的最佳分配為:

第1部分腦力: 1+2+3+4+5 = 15

第2部分腦力: 6+7 = 13

第3部分腦力: 8+9 = 17

其中耗時最多的一段是 17 天，因此答案是 17

範例測資2中，可以做的最佳分配為:

第1部分腦力: 13+24+27 = 64

第2部分腦力: 19+11+21 = 51

第3部分腦力: 29+15+8 = 52

其中耗時最多的一段是 64 天，因此答案是 64

分數分配

> 60% :1&lt;\=N&lt;\=1061&lt;=N&lt;=10^6

> 40% : 無其他限制

注意: 本題因為有常數問題，所以進行輸入輸出時，請用下列方式

1. 在using namespace std; 後面加上這段code

namespace io {
    const int SIZE = 1e7 + 10;
    char inbuff[SIZE];
    char *l, *r;
    inline void init() {
        l = inbuff;
        r = inbuff + fread(inbuff, 1, SIZE, stdin);
    }
    inline char gc() {
        if (l == r) init();
        return (l != r) ? *(l++) : EOF;
    }
    void read(int &x) {
        x = 0; char ch = gc();
        while(!isdigit(ch)) ch = gc();
        while(isdigit(ch)) x = x * 10 + ch - '0', ch = gc();
    }
} using io::read;

1. 把cin換成read()，cout換成printf()，用法如下:

read(N);
rean(M);
printf("%ld",ans);