대포알

시간 제한2초메모리 제한1024 MB

요약

숫자 직선 위에서 점프 패드에 튕기며 움직이는 Bessie가 깨뜨리는 목표물의 개수를 구합니다.

난이도: 보통10점 중 6점
유형: 시뮬레이션, 배열
정답자: 아직 제출이 없습니다

문제

Bessie는 대포알로 변신해 길이가 $N$ 인 수직선 위를 튕기며 이동하는 기술을 익혔습니다. ( $1 \leq N \leq 10^5$ ) 위치는 왼쪽에서 오른쪽으로 $1, 2, \dots, N$ 번 번호가 매겨져 있습니다. Bessie는 위치 $S$ ( $1 \leq S \leq N$ )에서 파워 1로 오른쪽을 향해 튕기기 시작합니다. Bessie의 파워가 $k$ 이면, 다음 튕김은 현재 위치에서 $k$ 만큼 앞으로 떨어집니다.

1부터 $N$ 까지의 모든 정수 위치는 표적 또는 점프 패드입니다. 각 표적과 점프 패드에는 0부터 $N$ 까지의 정수 값이 있습니다. 값이 $v$ 인 점프 패드에 닿으면 Bessie의 파워가 $v$ 만큼 늘고 진행 방향이 반대로 바뀝니다. 값이 $v$ 인 표적은 Bessie의 파워가 $v$ 이상인 상태로 닿으면 깨집니다. 표적에 닿아도 파워와 방향은 바뀌지 않습니다. 깨진 표적은 계속 깨진 상태로 남고, Bessie는 그 위를 파워와 방향을 바꾸지 않고 계속 튕길 수 있습니다.

Bessie가 무한히 튕기거나 수직선 밖으로 나갈 때까지 튕긴다면, 몇 개의 표적을 깨뜨립니까?

Bessie가 깰 수 있는 표적에서 시작하면 즉시 그 표적을 깹니다. 마찬가지로 점프 패드에서 시작하면 첫 번째 튕기기 전에 그 패드의 효과가 적용됩니다.

입력

첫 번째 줄에는 $N$ 과 $S$ 가 주어집니다. $N$ 은 수직선의 길이이고, $S$ 는 Bessie의 시작 위치입니다.

이어지는 $N$ 개의 줄은 각 위치를 설명합니다. $i$ 번째 줄에는 정수 $q_i$ 와 $v_i$ 가 주어집니다. 위치 $i$ 가 점프 패드이면 $q_i = 0$ , 표적이면 $q_i = 1$ 이며, $v_i$ 는 위치 $i$ 의 값입니다.

출력

깨지는 표적의 개수를 한 개의 정수로 출력합니다.

예제2

예제 1
입력
```
5 2
0 1
1 1
1 2
0 1
1 1
```
예상 출력
```
1
```
예제 2
입력
```
6 4
0 3
1 1
1 2
1 1
0 1
1 1
```
예상 출력
```
3
```