Mining on the Number Line

Little Blue is mining on a number line. There are n mining caves with coordinates \(a_i\) for \(i = 1, 2, \ldots, n\). He starts at coordinate \(0\) and can move left or right by 1 unit each step. When he passes by a cave for the first time, he mines it and collects 1 unit of ore (each cave can be mined only once). Given that the total distance moved cannot exceed \(m\), determine the maximum number of ore units he can collect.

Note: If there are multiple caves at the same point (including \(0\)), each is considered separately and can be mined once.

Hint: It is optimal to separate the caves into those to the left and those to the right of \(0\), and then try combining the two directions appropriately. For example, if you decide to collect \(l\) caves to the left (with the farthest being at \(-L\)) and \(r\) caves to the right (with the farthest being \(R\)), if \(l > 0\) and \(r > 0\) the minimal required distance is \(\min(2L+R, 2R+L)\). When only one side is visited, the required distance is just the farthest distance on that side.

inputFormat

The input consists of two lines:

• The first line contains two integers \(n\) and \(m\) \( (1 \leq n \leq 10^5,\ 0 \leq m \leq 10^9)\) representing the number of caves and the maximum distance that can be moved.
• The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) \(( -10^9 \leq a_i \leq 10^9 )\) which are the coordinates of the caves.

outputFormat

Output a single integer representing the maximum number of ore units Little Blue can collect without exceeding the total movement distance \(m\).

sample

1 1
1

1