EIU Programming Practices and Exams

Huy is a lumberjack, and there are N trees in front of him. He needs to chop at least M meters of wood using a machine that cuts tree parts above a certain height H. The machine leaves trees shorter than or equal to H intact. The goal is to find the maximum height H of the sawblade so that Huy gets at least M meters of wood.

Input

• The first line contains 2 integers N (number of trees, 1 ≤ N ≤ 10^6 ) and M (required wood, 1 ≤ M ≤ 2x10^9 ).
• The second line contains N integers: Heights of the trees (each < 10^9 ).

Output

A single number: the maximum height H of the sawblade.

Example

Input


Output




4 7 
20 15 10 17


15




5 20 
4 42 40 26 46


36