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?
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)~.
The only line of output is to contain one integer, the maximum length of the smallest piece.
Subtask 1 (30%)
~N \leq 10^3~
Subtask 2 (70%)
No further constraints.
5 3 5 2 6 9 3
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~.