Background

Special for beginners, ^_^

Description

有一个长度为n的整数序列A1...An,Ai可以为负数。将它们分成正好M 段. 设第i段的子序列和为Si(i=1..M).求一个拆分方法，使Max(S1.. Sm)最小

Format

Input

第一行二个整数N，M 1<=M<=N<=10000 接下来N个整数代表A1..An -10000<=Ai<=10000

Output

输出一个数代表Max(S1..Sm)

Samples

6 3 150 -50 1 101 1 100

101

Limitation

1s, 1024KiB for each test case.