Painting the Fence

Time limit2sMemory limit512 MB

Summary

Given n segment lengths on a cyclic fence of k boards, order the painters and place each segment to maximize the minimum number of boards each painter is first to paint.

Level: Hard8 of 10
Topics: Greedy, Binary search, Math, Implementation
Solved: No attempts yet

Problem

Tom Sawyer has persuaded $n$ of his friends to help him with the hard job of painting the fence around Aunt Polly's house. The fence consists of $k$ consecutive boards numbered from 1 to $k$ , and after board $k$ comes board 1 again.

Tom's friends are very picky: the $i$ -th friend agrees to take part in the painting only if he is allowed to paint a segment of exactly $a_i$ consecutive boards. Tom has only one brush, so the friends paint one after another and each paints his whole assigned segment at once. All Tom has to do is choose the order in which to invite the friends and choose for each one the desired number of consecutive boards.

Each of Tom's friends is ready to paint either a board that has not been painted yet or a board that one of his predecessors has already painted. Even so, the friends enjoy painting an unpainted board more. Tom wants to choose a number $x$ and distribute the fence segments for painting so that each of his friends paints at least $x$ unpainted boards. Tom loves his friends and wants each of them to get the most enjoyment out of the painting, so he tries to maximize $x$ .

Help Tom figure out how much joy he can bring his friends.

Input

The first line of the input file contains two integers $n$ ( $1 \le n \le 10^5$ ) and $k$ ( $1 \le k \le 10^9$ ). The next line contains $n$ integers, the values $a_i$ ( $1 \le a_i \le k$ ).

Output

Print a single number: the maximum possible value of $x$ .

Hint

In the first example $x = 5$ , because one of the friends simply does not want to paint more than five boards. He comes first, paints his five, and after that 10 unpainted boards go to Tom's second friend. Tom has to paint the remaining 85 boards himself.

In the second example, one way to reach $x = 2$ is as follows. First the third friend paints boards 4 through 6 (3 unpainted boards). Then the fourth friend paints boards 1 through 5 (3 unpainted boards). Then the second friend paints boards 1 through 8 (2 unpainted boards). Finally the first friend paints boards 6 through 10 and 1 through 2 (2 unpainted boards; note that the fence runs in a cycle, so these boards form a consecutive segment).

Examples2

Example 1
Input
```
2 100
5 10
```
Expected output
```
5
```
Example 2
Input
```
4 10
7 8 3 5
```
Expected output
```
2
```