406837: GYM102569 B Bonuses on a Line

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Bonuses on a Linetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

There are $$$n$$$ bonuses on a line: the $$$i$$$-th bonus is located at the point $$$x_i$$$. All coordinates of all bonuses are distinct. You are located at the point with the coordinate 0. How many bonuses can you collect in $$$t$$$ seconds, if you can pass the distance 1 in one second?

Input

The first line contains two integers $$$n$$$ and $$$t$$$ ($$$1 \le n \le 200000, 0 \le t \le 10^9$$$) — the number of bonuses and the time limit.

The second line contains $$$n$$$ integers $$$x_1$$$, $$$x_2$$$,..., $$$x_n$$$ ($$$-10^9 \le x_i \le 10^9$$$) — the coordinates of the bonuses. They are sorted in increasing order ($$$x_1 < x_2 < \ldots < x_n$$$).

Output

Output one integer — the maximum number of bonuses that can be collected in $$$t$$$ seconds.

ExampleInput
5 6
-4 -1 2 3 7
Output
3
Note

To collect 3 bonuses in $$$t = 6$$$ seconds, you must first collect the bonus with the coordinate -1, then the bonus with the coordinate 2, and in the end — the bonus with the coordinate 3. It will take you 5 seconds (1 second to collect the bonus with the coordinate -1, and 4 seconds to go from -1 to 3).

It is impossible to come to the bonus with the coordinate 7 in time. And if you first go to the bonus with the coordinate -4, you can collect only two bonuses (-4 and -1).

加入题单

上一题 下一题 算法标签: