Problem Description

Bessie has mastered the art of turning into a cannonball and bouncing along a number line of length $N$ ($1 \le N \le 10^5$), where positions are numbered from $1$ to $N$ from left to right. She starts at an integer position $S$ ($1 \le S \le N$) with an initial energy of $1$, moving to the right. If Bessie's energy is $k$, she will bounce to a position $k$ units ahead for her next bounce.

Each integer position from $1$ to $N$ contains either a target or a spring, each with an integer value between $0$ and $N$. A spring with value $v$ will increase Bessie's energy by $v$ and reverse her direction. A target with value $v$ will be broken if Bessie lands on it with energy not less than $v$. Landing on a target does not change Bessie's energy or direction. Broken targets remain broken, and Bessie can still bounce on them without changing her energy or direction.

How many targets will Bessie break if she bounces indefinitely or until she leaves the number line?

If Bessie starts at a target she can break, she will do so immediately. Similarly, if she starts at a spring, its effect will take place before her first bounce.

Input Format

The first line of input contains $N$ and $S$, where $N$ is the length of the number line and $S$ is Bessie's starting position.

The next $N$ lines describe each position. The $i$-th line contains integers $q_i$ and $v_i$, where $q_i = 0$ if position $i$ has a spring, and $q_i = 1$ if position $i$ has a target. $v_i$ is the value of the spring or target at position $i$.

Output Format

Output a single integer, the number of targets that will be broken.

Sample Input and Output

Sample Input #1

5 2
0 1
1 1
1 2
0 1
1 1

Sample Output #1

1

Sample Input #2

6 4
0 3
1 1
1 2
1 1
0 1
1 1

Sample Output #2

3

Notes

Sample Explanation 1

Bessie starts at position $2$, which is a target with value $1$, so she immediately breaks it. She then bounces to position $3$, which is a target with value $2$, so she cannot break it. She continues to bounce to position $4$, which changes her direction and increases her energy by $1$, reaching $2$. She bounces back to position $2$, which is already broken, so she continues. Now, she bounces to position $0$, so she stops. She breaks exactly one target, at position $2$.

Sample Explanation 2

Bessie's path is $4 \to 5 \to 3 \to 1 \to 6$, and her next bounce would take her off the number line ($11$). She breaks targets at positions $4, 3, 6$ in order.

Test Point Properties

• Test points $3-5$: $N \le 100$.
• Test points $6-10$: $N \le 1000$.
• Test points $11-20$: No additional restrictions.

见题面 Input 部分

见题面 Output 部分