Bạn được cho một danh sách n số nguyên dương \(a_1, a_2, ... a_n\). Bạn có thể thực hiện thao tác sau trên dãy số này: chọn bất kỳ phần tử nào và tăng hoặc giảm nó một đơn vị.

Tính toán chênh lệch giá trị tối thiểu có thể có giữa phần tử có giá trị lớn nhất và phần tử có giá trị bé nhất trong mảng đã cho nếu bạn có thể thực hiện thao tác nói trên không quá \(k\) lần.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) \((2 ≤ n ≤ 10^5, 1 ≤ k ≤ 10^{14})\) - số lượng phần tử trong dãy và số lần tối đa bạn có thể thực hiện thao tác tương ứng.

• Dòng thứ hai chứa một chuỗi các số nguyên \(a_1, a_2, ..., a_n ( 1 ≤ a_i ≤ 10^9)\).

Output

• in chênh lệch tối thiểu có thể có giữa phần tử tối đa và phần tử tối thiểu trong dãy nếu bạn có thể thực hiện thao tác nói trên không quá \(k\) lần

Example

4 5
3 1 7 5 

2

10 9
4 5 5 7 5 4 5 2 4 3

1