Sự Khác Biệt

Xem PDF

Điểm: 300 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

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\)\(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

Test 1

Input
4 5
3 1 7 5 
Output
2

Test 2

Input
10 9
4 5 5 7 5 4 5 2 4 3
Output
1

Bình luận


  • 5
    BichSonNhat    8:11 p.m. 30 Tháng 11, 2020

    Sao trong test \(k\) lại âm thế kia :v


    • 3
      TCA_Khoa    10:14 a.m. 1 Tháng 12, 2020

      em fix lại rồi a thử nộp lại xem