William the Alpaca is arranging a socially-distanced party with potential invitees. He would like to invite all of them, but alpacas are picky and they each have their own requirements. First, each alpaca demands to stand at a position , occupying a point on a straight line. On top of that, due to the rise of a nasty disease,
ALPACAVID-19, each alpaca has a range of , meaning they won't tolerate another alpaca being strictly less than units from their position. William wants to invite as many alpacas as possible, such that each invited alpaca satisfies the range requirement of every other invited alpaca. Help William find the maximum number of alpacas he can invite!
Subtask 1 [10%]
Subtask 2 [10%]
Subtask 3 [50%]
Subtask 4 [30%]
No additional constraints.
The first line contains one integer .
The next lines contain and for the alpaca.
Output one integer, representing the maximum amount of friends William will be able to invite.
Sample Input 1
5 4 2 14 4 7 5 3 3 13 1
Sample Output 1
Explanation for Sample 1
Alpaca and alpaca can be chosen. Alpaca 's range reaches and alpaca 's range reaches , so they are out of each other's ranges. Hence, this is valid, and it can be shown that this is one of the optimal arrangements.
Sample Input 2
7 19 3 4 8 6 5 20 13 14 4 13 7 1 4
Sample Output 2
Explanation for Sample 2
The optimal alpacas to keep are Alpacas , , , and .