Problem Description

There is a long stick lying horizontally with $ N - 1 $ notches. When this stick is cut at all the notches, it splits into $ N $ sticks of lengths $A_1, A_2, A_3, \dots, A_N$ from left to right.
You will choose some of the $ N - 1 $ notches to cut the stick before shipping it. (You may choose none or all of the notches.)
Since long sticks are cumbersome to handle, you want to ensure that all the sticks after cutting are no longer than $ L $. Also, to avoid uneven lengths, you want to make the shortest stick as long as possible after cutting.
Find the maximum possible length of the shortest stick after cutting.

Input Format

The input is given from the standard input in the following format:

$ N $ $ L $ $ A_1 $ $ A_2 $ $ A_3 $ $\dots$ $ A_N $

Output Format

Output the maximum possible length of the shortest stick after cutting.

Sample Input and Output

Sample Input #1

5 10
3 4 1 2 4

Sample Output #1

7

Sample Input #2

8 10
7 2 1 5 3 2 5 2

Sample Output #2

9

Sample Input #3

13 10000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output #3

6000000000

Notes/Hints

Constraints

• $1 \le N \le 2 \times 10^5$
• $1 \le L \le 10^{15}$
• $1 \le A_i \le \min(10^9, L)$
• All inputs are integers

Sample Explanation 1

Cutting only at the second notch from the left results in two sticks of lengths $ 3 + 4 = 7 $ and $ 1 + 2 + 4 = 7 $, making the shortest stick length $ 7 $. This is the maximum.

Sample Explanation 2

Cutting at the second and fifth notches from the left results in three sticks of length $ 9 $.

Sample Explanation 3

The optimal way to cut is to make one stick of length $ 6000000000 $ and one stick of length $ 7000000000 $.

见题面 Input 部分

见题面 Output 部分