Khufu has found himself lost in a desert. After long hours of navigating back home, he found himself losing valuable time to draw heiroglyphs for the Pharaoh!

Since Khufu cannot work for long hours under the scorching heat, he had to take breaks for shelter in between his working hours. He also hesitates to take a break in the middle of drawing a heiroglyph.

The Pharaoh ordered Khufu to only take ~k~ breaks as he is getting impatient. Can you help Khufu optimise his breaks so that the longest shift he has is minimised?

Input

The first line contains two integers ~n~ (~1 \le n \le 10^5~), the number of heiroglyphs Khufu needs to complete, and ~k~ (~0 \le k \le 10^9~), the number of breaks he can have.

The second line contains ~n~ integers ~a_i~ (~1 \le a_i \le 10^9~), the time in minutes Khufu needs to finish the ~i^{th}~ heiroglyph Pharaoh orders him to.

Output

Output the minimised longest shift Khufu has.

Clarification

• The total time Khufu needs to finish all Heiroglyphs is at most ~10^9~
• Khufu has to finish each heiroglyph in the order that Pharaoh orders him to.

Example

Input 1

5 1
3 5 7 10 8

Output 1

18

Given 1 break, Khufu has 2 shifts:

• In the 1st shift, Khufu completes the first 3 heiroglyphs, taking ~3 + 5 + 7 = 15~ minutes.
• In the 2nd shift, Khufu completes the remaining heiroglyphs, taking ~10 + 8 = 18~ minutes.

Therefore, the longest shift Khufu has is ~18~ minutes, which is the lowest possible time out of all possible times he can take a break.

Input 2

1 0
67

Output 2

67

Khufu can take no breaks, so the only option he has is to do the heiroglyph in one session.