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
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