Rounds

PerfectShape, a popular online group, gathers fans of workouts and a healthy lifestyle from all over the world. Every group member has earned a certain amount of credits on the trendy online sports platform M0V3, which gives them access to various workout and relaxation resources.

The amount of credits owned can differ greatly from one person to another. Since PerfectShape members value sharing and solidarity, they decide to redistribute credits by playing the following game.

The N group members are numbered from 1 to N, and the game consists of k rounds for some integer k with 1 ≤ k ≤ N. During the i-th round, every member except member i gives S credits to member i. The game may end after any round, and its outcome is the minimum amount of credits held by a member of the group after that round.

Find the maximum possible game outcome over all possible game endings.

The first line contains two integers N and S. Each of the following N lines contains a single integer; the (i + 1)-th line contains the amount of credits Ci that member i initially owns.

Print a single integer C, the maximum possible game outcome.

• 1 ≤ N ≤ 100 000
• 1 ≤ S ≤ 100 000 000
• for all i, 1 ≤ Ci ≤ 100 000 000 and S × (N − 1) ≤ Ci.

The game proceeds as follows:

• After round 1 the amounts of credits held are 44, 32, 28, and the minimum is 28.
• After round 2 the amounts of credits held are 34, 52, 18, and the minimum is 18.
• After round 3 the amounts of credits held are 24, 42, 38, and the minimum is 24.

The best possible outcome is therefore 28, which corresponds to ending the game after round 1.