Training Site
Sideways banner


Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 1.5 seconds

You are moving houses, and have packed your collection of mechanical keyboards into N boxes. But after you finished packing, you realised that you did not distribute the keyboards evenly between the N boxes, causing some of them to be too heavy to lift. Initially, box i contains x_i keyboards.

We define the imbalance of these boxes as the difference between the largest and the smallest number of keyboards inside any box. For example, if you had 3 boxes, with 9, 4, and 17 keyboards, their imbalance would be 17 - 4 = 13.

You would like to repack the boxes in such a way that minimizes their imbalance. As they are quite heavy, you can only move a single keyboard at a time. It takes one minute for you to move a single keyboard from any box to any other box. You have T minutes to repack the boxes before you need to leave.

What is the smallest imbalance you can achieve in T minutes?


The first line contains two space-separated integers, N (1 \le N \le 100\,000), the number of boxes, and T (1 \le T \le 1\,000\,000\,000), the number of minutes you have to repack the boxes.

The second line contains N space-separated integers, x_1, x_2, \dots, x_N (1 \le x_i \le 100\,000), the number of keyboards initially packed into each box.


You should print a single integer – the smallest imbalance you can achieve in T minutes.


  • Subtask 1 (30%): N, T \le 1\,000
  • Subtask 2 (30%): T \le 100\,000
  • Subtask 3 (40%): No further restrictions apply

Sample Explanation

In the first sample case, one possible solution is to move 2 keyboards from box 5 to box 1 (taking 2 minutes), and move 1 keyboard from box 4 to box 2 (taking 1 minute). This leaves the boxes with 4, 5, 5, 7, and 7 keyboards in order, which has an imbalance of 7 - 4 = 3.

In the second sample case, we can move 6 keyboards from box 3 to box 2. This leaves the boxes with 9, 10, and 11 keyboards in order, which has an imbalance of 11 - 9 = 2.

  • Sample Input 1

    5 3
    2 4 5 8 9

    Sample Output 1

  • Sample Input 2

    3 6
    9 4 17

    Sample Output 2