Picking flowers - MarisaOJ: Marisa Online Judge

On a field of flowers lies a coordinate axis with

n

$n$ blooming flowers. The

i^{t h}

$i^{th}$ flower is located at position

x_{i}

$x_i$ and takes

t_{i}

$t_i$ minutes to pick. These flowers will wither when it starts raining. It is known that it will rain after

m

$m$ minutes. Marisa starts at position

0

$0$ . Each minute, she can move one unit of distance. How many flowers can Marisa pick optimally? She can choose to skip picking certain flowers. ### Input - The first line contains two integers

n

$n$ and

m

$m$ . - The next

n

$n$ lines each contain two integers

x_{i}

$x_i$ and

t_{i}

$t_i$ . ### Output - Output a single integer representing the maximum number of flowers Marisa can pick. ### Constraints -

1 \leq n \leq 2 \times 10^{5}

$1 \le n \le 2 \times 10^5$ . -

1 \leq m, x_{i}, t_{i} \leq 10^{9}

$1 \le m, x_i, t_i \le 10^9$ . It is guaranteed that the values of

x_{i}

$x_i$ are distinct for all

i

$i$ 's. ### Example Input:

2121100066

$2 12 1 1000 6 6$

Output:

1

$1$

Containers C++ in Standard Template Library (STL)
	k-th element
	Dynamic prefix sum
	Unammed
	k-th occurence
	Set
	Most frequent value
	A lot of queries
	Median
	Houses
	Picking flowers

Topic

Sorting

Greedy

Data structure

Rating

1300

Solution (1)

Solution