Alan has a circular cake which he wants to share with his ~K~ friends. Unfortunately, this cake is notoriously difficult to cut, and thus the company who supplied the cake also included ~N~ dents in various locations that are easier to cut through. The ~N~ dents separate the cake into ~N~ sections each with an integer size ~a_i~. Since Alan is a good friend, after the cake is cut he will take the smallest remaining piece. However, Alan loves cake, so he wants to cut at ~K~ of the ~N~ dents such that the smallest remaining piece is as large as possible. Can you help him?

Input Specification

The first line contains two integers ~N\ (1 \leq N \leq 10^5),K (1 \leq K \leq N)~.

The next line contains ~N~ integers ~a_i\ (1 \leq a_i \leq 10^9)~.

Output Specification

The only line of output is to contain one integer, the maximum length of the smallest piece.

Subtasks

Subtask 1 (30%)

~N \leq 10^3~

Subtask 2 (70%)

No further constraints.

Sample Input

5 3
5 2 6 9 3

Sample Output

8

Sample Explanation

Alan cuts between ~5~ and ~2~, between ~6~ and ~9~, and between ~9~ and ~3~, leaving the cake with ~3~ pieces of size ~8~, ~9~, and ~8~.