Một ngày rảnh rỗi, Gấu quyết định làm ~N~ chiếc bánh để tặng crush. Bánh thứ ~i~ có độ ngon là ~A_i~, bánh có độ ngon càng lớn thì càng hấp dẫn. Để crush không bị hụt hẫng khi thử hết ~N~ chiếc bánh, Gấu muốn làm độ ngon chênh lệch giữa chiếc bánh ngon nhất và chiếc bánh tệ nhất là nhỏ nhất có thể. Thật may mắn, trong bếp của Gấu có đúng ~M~ hộp gia vị đặc biệt, có thể giúp Gấu tăng hoặc giảm độ ngon của bánh ~1~ đơn vị.

Yêu cầu: Hãy giúp Gấu tính toán độ ngon chênh lệch nhỏ nhất có thể sử dụng không quá ~M~ hộp gia vị đặc biệt.

Dữ liệu vào

• Dòng đầu tiên gồm ~2~ số nguyên ~N~, ~M~ ~(1 \le N \le 2 * 10^5,1 \le M \le 10^{14})~ lần lượt là số lượng bánh mà Gấu đã làm và số hộp gia vị đặc biệt mà Gấu có.
• Dòng thứ hai gồm ~N~ số nguyên ~A_i~ ~(1 \le i \le N, 1 \le A_i \le 10^9)~ là độ ngon của chiếc bánh thứ ~i~.

Dữ liệu ra

Gồm một số nguyên duy nhất là độ ngon chênh lệch nhỏ nhất có thể.

Tính điểm

• Subtask ~1~ (~20\%~ số điểm): ~1 \le N \le 100, 1 \le A_i \le 1000~
• Subtask ~2~ (~30\%~ số điểm): ~1 \le N \le 5000~
• Subtask ~3~ (~50\%~ số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

3 3
7 12 8

Output

2