dominó

Különböző magasságú dominók (x1,h1),...,(xN,hN) állnak az x tengelyen. Minden dominó úgy áll, hogy az alapja merőleges a tengelyre ami átmegy az alap középpontján. A k-adik dominó x koordinátája xk, magassága pedig hk (k=1...N). Nincsen két dominó ugyanazon a helyen. Ha meglökünk egy (xk,hk) dominót jobbra (a tengely mentén pozitív irányba) akkor minden olyan dominót közvetlenül felborít melyek tőle jobbra vannak és az xk-tól vett távolságuk szigorúan kisebb mint hk. Hasonlóan ha ugyanezt a dominót balra lökjük meg, akkor minden olyan dominót közvetlenül felborít melyek tőle balra vannak és az xk-tól vett távolságuk szigorúan kisebb mint hk. Világos, hogy ezeken kívül még felboríthat más dominókat is közvetett módon.

Maximálisan hány dominót tudunk feldönteni (M) ha legfeljebb 2 dominót választhatunk, és egymástól függetlenül jobbra vagy balra meglökjük őket?

1. Példa

        x   h
       10  10
       16   5
       18   2
       20   5

A (10,10) jobbra döntésével minden dominót feldöntünk, ezért M=4.

2. Példa

         x   h
         0   3
         2   1
        10   3
         8   3
       100   1
     -1000   1

Itt is 4 a válasz ami (0,3) jobbra illetve a (10,3) dominó balra döntésével érhető el. Átgondolható, hogy ettől jobbat nem találhatunk.

3. Példa

         x     h
        -7     1
        -5     3
        -1     5
         1     5
         5     3
         7     1        

Minden dominó feldönthető a (-1,5) balra és (1,5) jobbra dominó meglökésével.

A bemenet specifikációja

N
x1 h1
...
xN hN

Az első sor az 1 ≤ N ≤ 105 szám. A következő N sorban a szóközzel elválasztott -108 ≤ xk ≤ 108 és 1 ≤ hk ≤ 108 mennyiségek vannak k=1...N. A dominók tetszőleges sorrendben adottak.

A kimenet specifikációja

M

Egyetlen sor a keresett M-mel.

1. példa bemenet

1. 4
2. 16 5
3. 20 5
4. 10 10
5. 18 2

letöltés szöveges állományként

1. példa kimenet

1. 4

letöltés szöveges állományként

2. példa bemenet

1. 6
2. 0 3
3. 2 1
4. 10 3
5. 8 3
6. 100 1
7. -1000 1

letöltés szöveges állományként

2. példa kimenet

1. 4

letöltés szöveges állományként

3. példa bemenet

1. 4
2. 1 1
3. 2 1
4. 3 1
5. 4 1

letöltés szöveges állományként

3. példa kimenet

1. 2

letöltés szöveges állományként