Language C programming, just use library stdio.h only, USE MERGE SORTING

Wood

Jojo is a carpenter and now he needs X metres of wood. He is now in a forest with N trees with integer height in metres, A1, A2, . . . , AN . He has a special cutting device. The device can be set to a certain height H. After that, it can cuts all the tree that has height more than H at the same time. Then, he will collect the parts that were cut off. Since he is lazy, he only wants to use the cutting device once. Help him to find the maximum integer height H for the device such that the sum of parts that is cut off is at least X meters. It is guaranteed that the sum of all of the tree heights will be more than or equal to X.

Format Input

The first line consist of two integers, N and X. The second line consist of N integers, A1, A2, . . . , AN , the height of the trees in metres.

Format Output

Output 1 line which consists of an integer H, which is the maximum integer height for the device such that the sum of the parts that will be collected is at least X meters.

Constraints

1 N 105

1 Ai , X 1012

Sample Input 1 (standard input)

7 10

1 1 2 3 3 3 3

Sample Output 1 (standard output)

0

Sample Input 2 (standard input)

7 10

2 2 2 3 3 3 3

Sample Output 2 (standard output)

1