베시는 포탄으로 변신하여 길이가 \(N\)인 수직선을 따라 튀어 다니는 기술을 익혔다. (\(1\le N\le 10^5\)) 수직선의 위치에는 왼쪽부터 오른쪽까지 \(1,2,\ldots,N\)의 번호가 붙어 있다. 베시는 정수 위치 \(S\)에서 오른쪽을 향해 시작하며, 처음 힘은 \(1\)이다. (\(1\le S\le N\)) 베시의 힘이 \(k\)라면 다음에는 현재 위치에서 진행 방향으로 \(k\)만큼 떨어진 위치로 튀어 이동한다.

\(1\)부터 \(N\)까지의 각 정수 위치에는 표적 또는 점프대가 하나씩 있다. 각 표적과 점프대에는 \(0\) 이상 \(N\) 이하의 정숫값이 적혀 있다. 값이 \(v\)인 점프대에 도착하면 베시의 힘이 \(v\)만큼 증가하고 진행 방향이 반대로 바뀐다. 값이 \(v\)인 표적에 도착했을 때 베시의 힘이 \(v\) 이상이면 그 표적이 부서진다. 표적에 도착해도 베시의 힘과 진행 방향은 바뀌지 않는다. 한 번 부서진 표적은 계속 부서진 상태로 남으며, 베시는 이후에도 그 위치에 도착할 수 있다. 이 경우에도 힘과 진행 방향은 바뀌지 않는다.

베시가 무한히 튀어 다니거나 수직선을 벗어날 때까지 이동한다면, 부서지는 표적은 모두 몇 개인지 구하여라.

베시가 시작한 위치에 부술 수 있는 표적이 있다면 즉시 그 표적을 부순다. 마찬가지로 시작 위치에 점프대가 있다면 첫 번째 점프 전에 그 점프대의 효과가 적용된다.

입력

첫째 줄에 수직선의 길이 \(N\)과 베시의 시작 위치 \(S\)가 공백으로 구분되어 주어진다.

다음 \(N\)개의 줄에 각 위치의 정보가 주어진다. 이 중 \(i\)번째 줄에는 두 정수 \(q_i\)와 \(v_i\)가 공백으로 구분되어 주어진다. 위치 \(i\)가 점프대이면 \(q_i=0\)이고, 표적이면 \(q_i=1\)이다. \(v_i\)는 위치 \(i\)에 있는 점프대 또는 표적의 값이다.

출력

부서지는 표적의 수를 출력한다.

예제 입력 1

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

예제 출력 1

1

베시는 값이 \(1\)인 표적이 있는 위치 \(2\)에서 시작하므로 그 표적을 즉시 부순다. 이후 위치 \(3\)으로 이동한다. 위치 \(3\)의 표적 값은 \(2\)이므로 이 표적은 부술 수 없다. 계속해서 위치 \(4\)로 이동하면 진행 방향이 반대로 바뀌고 힘이 \(1\) 증가하여 \(2\)가 된다. 베시는 이미 부서진 표적이 있는 위치 \(2\)로 되돌아온 뒤 계속 이동한다. 이때 다음 위치는 \(0\)이므로 수직선을 벗어나 이동을 멈춘다. 베시는 위치 \(2\)의 표적 하나만 부순다.

예제 입력 2

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

예제 출력 2

3

베시가 이동하는 경로는 \(4\to5\to3\to1\to6\)이다. 다음 이동 위치는 수직선 밖의 \(11\)이므로 이동을 멈춘다. 베시는 위치 \(4\), \(3\), \(6\)의 표적을 이 순서대로 부순다.

서브태스크

출처

USACO 2024 January Contest, Bronze, Problem 2. Cannonball