Tom Sawyer persuaded n of his friends to help him in the difficult task of painting the fence surrounding Aunt Polly's house. The fence consists of k consecutive boards, numbered from 1 to k, and after the k-th board comes the first one again.
Tom's friends are very fastidious, the i-th friend agrees to participate in painting only if he is allowed to paint a section of exactly ai consecutive boards. Tom has only one brush, so his friends will paint in turn and at once the entire segment allotted to them. The only thing left for Tom to do is choose the order in which to invite his friends, as well as choose the desired number of consecutive boards for each.
At the same time, each of Tom's friends is ready to paint both an unpainted fence board and a board that has already been painted by one of his predecessors. However, friends get more pleasure from painting an unpainted board. Tom wants to choose a number x and distribute the fence sections to be painted in such a way that each of his friends paints at least x unpainted planks. Tom loves his friends very much and wants each of them to get the most out of painting the fence, so he tries to maximize x.
Help Tom understand how much joy he can bring to his friends.
Input data format
The first line of the input file contains two integers n (1 ≤ n ≤ 10
5 ) and k (1 ≤ k ≤ 10
9 ). The next line contains n integers — values a
i (1 ≤ a
i ≤ k).
Output data format
Print one number — maximum possible value of
x.
| Input |
Output |
2 100
5 10
| 5 |
4 10
7 8 3 5
| 2 |
Explanation
In the first example x = 5 because one of the friends just doesn't want to paint more than five boards. He will come first, paint his five, after which another 10 unpainted boards will go to Tom's second friend. The remaining 85 boards will have to be painted by Tom himself.
In the second example, x = 2 can be reached, for example, like this. First, the third friend paints boards 4 to 6 (3 unpainted boards). Then the fourth friend paints boards 1 to 5 (3 unpainted boards). Then the second friend paints boards 1 to 8 (2 unpainted boards). Finally, the first friend paints boards 6 to 10 and 1 to 2 (2 unpainted boards, note that the fence goes in a cycle and these boards form a consecutive segment).