Imbalance

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?

Input

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.

Output

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

Subtasks

• 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$.