Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×
ZE. Array Division
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array containing $$$n$$$ positive integers.

Your task is to divide the array into $$$k$$$ subarrays so that the maximum sum in a subarray is as small as possible.

Input

The first input line has two integers $$$n$$$ and $$$k$$$.

The next line has $$$n$$$ integers $$$x_1,x_2,\dots,x_n$$$: the contents of the array.

Constraints:

  • $$$1 \le k \le n \le 2 \cdot 10^5$$$
  • $$$1 \le x_i \le 10^9$$$
Output

Print one integer: the maximum sum in a subarray in the optimal division.

Example
Input
5 3
2 4 7 3 5
Output
8