问题描述

Bessie 已经精通了变成炮弹并沿着长度为 $N$（$1 \leq N \leq 10^5$）的数轴弹跳的艺术，数轴上的位置从左到右编号为 $1, 2, \ldots, N$。她从某个整数位置 $S$（$1 \leq S \leq N$）开始，以 $1$ 的起始能量向右弹跳。如果 Bessie 的能量为 $k$，则她将弹跳至距当前位置向前距离 $k$ 处进行下一次弹跳。

从 $1$ 到 $N$ 的每个整数位置上均有炮击目标或跳板。每个炮击目标和跳板都有一个在 $0$ 到 $N$ 范围内的整数值。一个数值为 $v$ 的跳板会使 Bessie 的能量增加 $v$ 并反转她的方向。一个数值为 $v$ 的炮击目标会在着陆时能量不小于 $v$ 时被击破。着陆在炮击目标上不会改变 Bessie 的能量和方向。被击破的炮击目标将保持击破状态，Bessie 依然可以在该炮击目标上弹跳，同样不会改变能量和方向。

如果 Bessie 弹跳无限长的时间或直到她离开数轴，她会击破多少个炮击目标？

如果 Bessie 开始时位于一个她可以击破的炮击目标，她会立刻这样做。类似地，如果 Bessie 开始时位于一个跳板，跳板的效果将在她第一次跳跃之前生效。

输入格式（从终端 / 标准输入读入）

输入的第一行包含两个整数 $N$ 和 $S$，其中 $N$ 为数轴的长度，$S$ 为 Bessie 的起始位置。 以下 $N$ 行描述了每一个位置。其中第 $i$ 行包含整数 $q_i$ 和 $v_i$，如果位置 $i$ 上有一个跳板则 $q_i=0$，位置 $i$ 上有一个炮击目标则 $q_i=1$，$v_i$ 是位置 $i$ 上的跳板或炮击目标的数值。

输出格式（输出至终端 / 标准输出）

输出一个整数，为将被击破的炮击目标数量。

输入样例 1

输入样例

样例 1

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

3

解释

Bessie 经过的路径为 $4 \rightarrow 5 \rightarrow 3 \rightarrow 1 \rightarrow 6$，下一次弹跳将会使她离开数轴（$11$）。她依次击破了炮击目标 $4, 3, 6$。

测试点性质

• 测试点 3-5：$N \leq 100$。
• 测试点 6-10：$N \leq 1000$。
• 测试点 11-20：没有额外限制。

来源

USACO真题2024-01