Poisoned Dagger

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

A dragon has $h$ HP. Attacks happen at strictly increasing seconds $a_i$. Each attack starts a poison lasting $k$ seconds and dealing one damage per second; a new attack cancels any remaining old poison and restarts it. Find the minimum integer $k$ causing at least $h$ total damage.

Input

The first line contains $n,h$. The second line contains $a_1,\ldots,a_n$.

Output

Print the minimum $k$.

Subtasks

• Subtask 1 — 20%: $n\le10$, $h\le10^6$.
• Subtask 2 — 30%: $h\le10^{12}$.
• Subtask 3 — 50%: $n\le100$, $h\le10^{18}$, $a_i\le10^9$.

Example

Input

3 10
2 4 10

Output

4

Explanation

For $k=4$, the three attacks contribute 2, 4, and 4 damage.