TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

Description

這裡是收錄所有的語言的巴貝爾塔(Tower of Babel)。塔內,有 $M$ 個僧人在值班,需要抄錄 $N$ 本書,編號從 $1$ 至 $N$。在已經知道第 $i$ 本書會花 $t_i$ 天抄錄完畢,而且所有的僧人都要抄錄連續編號的書的情況之下,請問這些僧人最短需要花多少時間才能夠將這些書全部抄錄完畢?請假設工作分配完畢之後,所有的僧人就會同時開始抄錄,並且會晝夜不停地抄錄,而且這些僧人只會抄錄自己被分配到的那些書。請注意,抄錄結束的時間是從所有僧人都開始抄錄開始,直到最後一個僧人抄完最後一本書為止。

Input Format

輸入有兩行。第一行有兩個正整數 $N$ 和 $M(1 \leq N, M \leq 2 \times 10^ 5)$,分別代表書本的數量和僧人的數量。第二行有 $N$ 個正整數 $t_1,t_2,t_3,\ldots,t_N(1 \leq t_i \leq 10^ 9)$ 依序代表書本需要抄錄的時間。

Output Format

請輸出一個正整數,代表這些僧人所需要的最短時間。

Sample Input 1

7 2
1 2 3 4 5 6 7

Sample Output 1

15

Sample Input 2

4 4
7 1 2 2

Sample Output 2

7

Sample Input 3

3 4
49 98 7777714

Sample Output 3

7777714

Hints

Problem Source

UVa 714

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~23 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2
1 2000 524288 65536 1 2
2 2000 524288 65536 1 2
3 2000 524288 65536 2
4 2000 524288 65536 2
5 2000 524288 65536 2
6 2000 524288 65536 2
7 2000 524288 65536 2
8 2000 524288 65536 2
9 2000 524288 65536 2
10 2000 524288 65536 2
11 2000 524288 65536 2
12 2000 524288 65536 2
13 2000 524288 65536 2
14 2000 524288 65536 2
15 2000 524288 65536 2
16 2000 524288 65536 2
17 2000 524288 65536 2
18 2000 524288 65536 2
19 2000 524288 65536 2
20 2000 524288 65536 2
21 2000 524288 65536 2
22 2000 524288 65536 2
23 2000 524288 65536 2