Number of Suitable Locations

Given the distribution center coordinates centers, the warehouse must be placed at an integer position from −10^9 to 10^9 (inclusive). It makes a separate round trip to each center, so the total distance is 2·Σ|center[i]−warehouse|. Find the number of warehouse positions whose total distance does not exceed d.

输入格式

The first line contains n d and the second line contains centers. The original bounds are 1≤n≤100000, −10^9≤centers[i]≤10^9, 0≤d≤10^15. The original bounds on positions along the number line are kept and are not extended to an infinite integer line.

输出格式

Output a single integer, the answer.

样例 1

输入：

1 4
0

输出：

5

样例 2

输入：

2 8
-2 2

输出：

5

样例 3

输入：

2 1
0 5

输出：

0

样例说明

The answers are 5, 5 and 0. In the second example every point from −2 to 2 has a total round-trip distance of 8. No matter how large the budget is, positions outside the original ±10^9 number line cannot be counted.