문제

젊은 마린(Marin)은 유명한 레스토랑 ‘Plavi 9’에서 보조 요리사로 일하고 있다. 이 식당의 오늘의 메뉴에는 속을 채운 고추 요리(stuffed peppers)가 포함되어 있다.

모든 보조 요리사들은 고추가 어릴 때 속을 채워야 맛있다는 것을 알고 있기 때문에, 마린은 X일 이하의 어린 고추만 요리에 사용하기로 했다. 그 외의 고추들은 신선한 상태로 애피타이저로 제공할 예정이다.

다행히도 크로아티아가 EU에 가입한 이후 새로운 법이 시행되었다. 이 법에 따르면 모든 고추는 언제나 자신의 신분증(ID 카드)을 가지고 있어야 한다. 마린은 고추의 ID 카드를 보고 고추의 나이를 쉽게 알 수 있다.

잘 알려지지 않은 사실이지만, 고추들도 각자의 인생 목표와 꿈을 가지고 있다. 더 정확히 말하면, 모든 고추는 어릴 때부터 자신이 나중에 신선한 고추로 제공되고 싶은지, 아니면 속을 채운 고추가 되고 싶은지를 알고 있다.

현재 속을 채워지기 위해 줄을 서 있는 N개의 고추들이 겪는 문제를 당신은 알고 있다.

• 어떤 고추는 속을 채운 요리가 되고 싶지만 너무 늙었다.
• 어떤 고추는 신선하게 제공되고 싶지만 속이 채워질 예정이다.

고추들은 마린의 기준값 X를 모르기 때문에, 다음과 같은 전략으로 이 부당함을 해결하려고 한다.

• 첫 번째 고추는 두 번째 고추와 ID 카드를 바꾸려고 시도한다.
• 두 번째 고추는 세 번째 고추와 시도한다.
• 이런 식으로 줄 끝까지 진행된다.

서로 ID 카드를 교환하는 조건은 다음과 같다.

• 현재 더 큰 번호(더 많은 나이)가 적힌 ID 카드를 들고 있는 고추가 “속을 채운 고추(1)”가 되고 싶어하고,
• 더 작은 번호의 ID 카드를 들고 있는 고추가 “신선한 고추(0)”가 되고 싶어할 때

두 고추는 ID 카드를 교환한다.

단, ID 카드의 숫자가 같으면 교환하지 않는다.

당신의 임무는 최종적으로 자신의 인생 목표를 이루게 되는 고추의 수를 구하는 것이다.

입력

• 첫 번째 줄에 정수 N, X (1 ≤ N, X ≤ 1000)가 주어진다.

  • N: 고추의 개수
  • X: 속을 채울 수 있는 최대 나이

• 다음 N개의 줄에는 두 정수 a, b가 주어진다.

  • a (1 ≤ a ≤ 1000): 고추 ID 카드에 적힌 나이(일 수)

  • b (0 또는 1): 고추의 인생 목표

    • 0 → 신선하게 제공되고 싶음
    • 1 → 속을 채운 고추가 되고 싶음

출력

자신의 인생 목표를 이룬 고추의 수를 출력한다.

예제 입력 1

4 5
2 0
3 0
4 0
5 0

예제 출력 1

0

예제 입력 2

5 5
3 1
2 0
13 1
2 0
10 1

예제 출력 2

5

예제 입력 3

6 10
15 1
12 1
8 0
10 1
3 0
1 1

예제 출력 3

4