favorite We need a little bit of your help to keep things running, click on this banner to learn more

2019-2020 Azerbaijan Finals, June 17


5000 years later, when the coronavirus epidemic was stopped, n skyscrapers are planned to be built in Baku. We will represent Baku as the coordinate axis of numbers. For each skyscraper, its coordinate (xi) and height (hi) are given. Engineers consider the skyscraper "unprofitable" if to the left of it at a distance of no more than d, and also to the right of it at a distance of no more than d, there is a skyscraper which height is at least twice more than the height of a given skyscraper (this skyscraper itself may be unprofitable). Such skyscrapers are considered unsuccessful from a business point of view, so engineers plan to build some other facility instead. You must calculate the number of "unprofitable" skyscrapers so that the engineers know their job.


First line contains two numbers n (1n105) and d (1d109). Next d lines contain integers xi and hi (1xi, hi109 ). All coordinates of skyscrapers are different.


Print the number of unprofitable skyscrapers.

Time limit 1 second
Memory limit 128 MiB
Input example #1
6 4
10 3
6 2
5 3
9 7
3 6
11 2
Output example #1
Author Rafael Sadatimov
Source 2019-2020 Azerbaijan Finals, June 17