Dao tẩm độc (Poisoned Dagger)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một con rồng có $h$ máu. Có $n$ lần đâm tại các giây tăng nghiêm ngặt $a_1<a_2<\cdots<a_n$.

Một lần đâm áp dụng độc trong $k$ giây, gây $1$ sát thương ở mỗi giây bắt đầu từ chính giây bị đâm. Nếu một lần đâm mới xảy ra khi độc cũ còn hiệu lực, hiệu ứng cũ bị hủy và được thay bằng hiệu ứng mới.

Hãy tìm số nguyên $k$ nhỏ nhất để tổng sát thương ít nhất $h$.

Input

Dòng đầu chứa $n,h$. Dòng thứ hai chứa $a_1,\ldots,a_n$.

Output

In $k$ nhỏ nhất.

Subtask

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

Ví dụ

Input

3 10
2 4 10

Output

4

Giải thích

Với $k=4$, ba hiệu ứng gây sát thương trong các đoạn $[2,3]$, $[4,7]$, $[10,13]$, tổng cộng $2+4+4=10$.