우산

넥슨에서 일하는 배찌는 요즘 아주 바쁘다. 오늘 하루도 넥슨의 $N$개 건물을 오가며 수 많은 회의에 참여했다. 특히 건물에는 각각 번호가 붙어있는데, 배찌는 오늘도 $B_0$번 건물에 출근해서 건물을 $M$번 오가고 있다. 이때 건물을 이동한 순서대로 $B_1$, $B_2$, $\cdots$, $B_M$이라고 하자.

요즘 날씨가 변덕스럽기 때문에, 건물을 오가는 잠깐 동안 비가 와서 우산이 필요한 때가 있다. 정확히, $B_{i-1}$번 건물에서 $B_i$번 건물로 이동하려고 했을 때 배찌의 판단에 따른 우산의 필요 여부를 $R_i$라고 하자. $R_i=0$ 이면 우산이 필요하지 않았음을, $R_i=1$ 이면 우산이 필요했음을 의미한다.

배찌는 건물을 나갈 때 만약 우산이 필요하지 않다면 우산을 가지지 않고 바로 다음 건물로 이동한다. 반대로 우산이 필요한 경우, 건물 내 개인 물품 보관함에 이미 보관된 우산이 하나라도 있다면 그 중 하나를 들고 다음 건물로 이동하고, 보관된 우산이 하나도 없다면 건물 내 편의점에서 새로운 우산을 하나 사서 다음 건물로 이동한다. 그리고 우산을 들고 이동하면, 건물에 도착했을 때 해당 건물 내 개인 물품 보관함에 가지고 온 우산을 보관한다.

오늘 하루의 이동을 나타내는 $B$와 $R$이 주어진다. 모든 건물의 개인 물품 보관함에 배찌의 우산이 하나도 없었다고 할 때, 배찌가 오늘 몇 개의 우산을 구매했는지 구하는 프로그램을 작성해보자.

입력 형식

첫 줄에 세 자연수 건물의 수 $N$, 이동 횟수 $M$, 출근한 건물 $B_0$이 공백으로 구분되어 주어진다. ($2 \le N \le 10$; $1 \le M \le 200$; $1 \le B_0 \le N$)

다음 $M$개의 줄의 $i$번째 줄에는 $i$번째로 이동한 건물 $B_i$와 이동 당시 우산의 필요 여부 $R_i$가 공백으로 구분되어 주어진다. ($1 \le B_i \le N$; $0 \le R_i \le 1$; $B_{i-1} \ne B_i$)

출력 형식

첫 줄에 오늘 하루 배찌가 구매한 우산의 개수를 출력한다.

예제

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

2

채점 방식

이 문제는 모든 케이스를 맞추는 경우에만 만점을 받고, 그렇지 않으면 $0$점을 받는다.

해설