Pastries

Interview

Time limit2sMemory limit1024 MB

Summary

Find the maximum number of pastries Scrooge can eat within T seconds, starting at coordinate 0 on a line where each pastry at x_i takes t_i to eat.

Level: Medium5 of 10
Topics: Greedy, Heap, Sorting
Solved: No attempts yet

Problem

Today is Scrooge's birthday.

As a gift, he received an entire table of pastries. Millionaires have little free time, so Scrooge wants to eat as many pastries as possible in $T$ seconds.

The table is an infinite line. Each pastry is placed at coordinate $x_i$ . Moving from pastry $i$ to pastry $j$ takes $|x_i - x_j|$ seconds. Eating pastry $i$ takes $t_i$ seconds. Pastries at the same point need no movement between them, but they must be eaten one at a time.

Scrooge starts at coordinate $0$ . Find the maximum number of pastries he can eat within $T$ seconds.

Input

The first line contains two integers $n$ and $T$ ( $1 \le n \le 100\,000$ , $1 \le T \le 10^9$ ), the number of pastries and the available time.

Each of the next $n$ lines contains two integers $x_i$ and $t_i$ ( $1 \le x_i, t_i \le 10^9$ ), the coordinate of the $i$ -th pastry and the time needed to eat it. The pastries are given in non-decreasing order of coordinate, that is, $x_i \le x_j$ whenever $i < j$ .

Output

Print one line with the maximum number of pastries Scrooge can eat within $T$ seconds.

Hint

In the first sample, Scrooge goes from coordinate $0$ to coordinate $1$ , eats the first pastry, then moves to coordinate $3$ and eats the third pastry.

Examples3

Example 1
Input
```
3 10
1 4
2 5
3 3
```
Expected output
```
2
```
Example 2
Input
```
3 10
1 2
2 2
3 3
```
Expected output
```
3
```

Example 3

Input

Expected output