Maximize Garden Defense Value

DreamGrid and BaoBao are playing a variant of Plants vs. Zombies. In DreamGrid's garden, there are n plants arranged in a line; the i-th plant is at position i (in meters) from his house (position 0). Each plant has two parameters: a growth speed a_i and a defense value d_i. Initially, all defense values are zero. Each time a plant is watered, its defense increases by its growth speed, that is, d_i increases by a_i.

DreamGrid controls a robot initially situated at his house. In one step, he chooses a direction (east or west) and the robot moves exactly 1 meter in that direction. Important: The robot must move before watering. After moving, if the robot’s current position matches a plant’s position, the plant is watered immediately.

The robot is limited to at most m steps. The defense value of the entire garden is defined as \[ \min_{1 \le i \le n} d_i \] DreamGrid’s goal is to plan a route for the robot so that the minimum defense value among all plants is maximized.

Note: The robot can travel arbitrarily far beyond the garden (even going west of the house), and may pass the same plant multiple times. Every time the robot lands on a plant’s position, it waters the plant (adding its growth speed to the plant’s defense).

Hint: One way to solve the problem is to use a binary search on the candidate defense value and a greedy simulation to check if it is possible to achieve that value within m steps. In particular, if you aim for a minimum defense value of \(X\), then for each plant you need to water it at least \(\lceil X / a_i \rceil\) times. During an initial eastward pass, every plant gets watered once. For any additional required waterings, an effective strategy is to perform round-trip moves from the easternmost plant to the leftmost plant that still needs extra waterings. Each such round trip from plant at position \(L\) (the leftmost plant that requires extra watering) to the easternmost plant (at position \(n\)) costs \(2(n - L)\) steps and waters all plants from \(L\) to \(n\) one extra time.

Your task is to compute the maximum achievable minimum defense value of the garden.

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁹), the number of plants and the maximum number of robot steps available.

The second line contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹), where a_i is the growth speed of the i-th plant.

outputFormat

Output a single integer — the maximum achievable minimum defense value of the garden.

Explanation: If the answer is X, then it is possible to ensure that after at most m steps, every plant has been watered enough times so that its defense value is at least \(X\), and \(X\) is maximized.

sample

3 23
1 2 3

6