BOOKS

Before the invention of typography, copying books was a very laborious process. All pages had to be handwritten by specialized individuals called scribes. The librarian of the Library of Alexandria has a stack of ~N~ classical works that need to be copied. For this purpose, he has at his disposal ~K~ scribes. Each work may differ in the number of pages, and each scribe can only take continuously adjacent books from the stack. The librarian knows the number of pages of each book and must distribute the books to the scribes in order to minimize the maximum number of pages copied by any scribe. Write a program to solve the librarian's problem.

Input

The first line of input will contain two positive integers, the number of books ~N~ and the number of scribes ~K~. The next ~N~ lines will contain ~N~ positive integers ~A_i~, one per line, representing the number of pages of book ~i~.

Output

The output should consist of a single line containing exactly one integer, the maximum number of pages that any scribe will copy.

Constraints

~1 \le N \le 100.000~, ~1 \le K \le N~, ~1 \le A_i \le 10.000~.
Execution time limit: 1 sec.
Maximum available memory: 64 MB.

Example of Input - Output

STDIN (books.in)

5 2
10
20
40
10
50

STDOUT (books.out)

70

Explanation of the Example

The optimal solution is to assign the first three books to the first scribe and the remaining two books to the second scribe. Thus, the maximum number of pages that any scribe will copy is ~70~ ~(10 + 20 + 40)~.