Atmospheric Pressure Subset Selection

Bessie, known as the Baric Bovine, takes N measurements of atmospheric pressure during the day in order to impress Farmer John. She wishes to select a subset of these measurements such that the overall error in representing the entire set is no more than E. The error is calculated as follows for every measurement that is not chosen:

• If the measurement occurs before the first selected measurement, say at index \( s_1 \), then its error is \( 2\,|M_i - M_{s_1}| \).
• If the measurement is between two consecutive selected measurements \( M_{s_j} \) and \( M_{s_{j+1}} \), its error is \( \left|2M_i - \left(M_{s_j} + M_{s_{j+1}}\right)\right| \).
• If the measurement occurs after the last chosen measurement, say \( s_K \), its error is \( 2\,|M_i - M_{s_K}| \).

Your task is to determine the smallest possible number of measurements (i.e. the smallest \( K \)) that Bessie can choose so that the sum of errors is at most \( E \). It is guaranteed that taking all measurements results in zero error, so a solution always exists.

inputFormat

The first line contains two integers \( N \) and \( E \) where \( 1 \leq N \leq 100 \) and \( 1 \leq E \leq 1,000,000 \).

The second line contains \( N \) integers \( M_1, M_2, \ldots, M_N \) (each between 1 and 1,000,000), representing the atmospheric pressure measurements in the order they were taken.

outputFormat

Output a single integer: the smallest number of measurements that can be selected so that the total error is at most \( E \).

sample

5 10
1 2 3 4 5

2