고추

프로그램 명: coci_paprika

제한시간: 1 초

[요약] n개의 고추가 각각 삶의 목표를 가지고 있다.

삶의 목표는 0과 1로 입력된다.

0:자신의 번호가 X보다 높게 되는것
1:자신의 번호가 X보다 낮거나 같게 되는것

이때, 고추들은 꿈을 이루는 고추의 수가 가장 많게 하기 위하여 다음과 같이 하도록 결정하였다.

각각의 고추는 자신의 다음에 있는 고추와 번호를 바꾸었을때 둘 다 삶의 목표를 이룰 수 있는경우 번호를 바꾸기로 한것이다!! 번호 바꾸기가 모두 끝난 뒤 자신의 삶의 목표를 달성할 고추의 수를 구하는 것이 문제이다.

입력

첫번째 줄에 n과 X가 입력된다.
그 이후 N줄에 각 고추의 번호와 삶의 목표가 입력된다.

출력

삶의 목표를 달성할 고추의 수를 출력한다.

Young Marin is working as an assistant chef in a popular restaurant called Plavi 9 where the daily offer includes, among other things, stuffed peppers. Every assistant chef knows that the peppers are stuffed when they are young, so he decided to prepare the meal using only peppers not older than X days. Marin will serve all the other peppers fresh, as an appetizer. Luckily, as Croatia entered the EU, there is a new law enforced. The law states that every pepper has to have its ID card at any moment. Marin can easily determine the age of a pepper by looking at its ID card.

It is less known that peppers have, besides official documents, their own life purposes and ambitions. More precisely, every pepper knows from an early age whether they want to be served as a fresh or stuffed pepper when they grow up. Bearing that in mind, you are aware of the problems N peppers are facing while waiting in line to be filled. The life purpose of some peppers is to be a part of the dish, but they are too old, and some peppers want to be served fresh, but will be filled.

Because the peppers aren’t aware of Marin’s number X, they have decided to rectify the injustice using the following strategy. The first pepper tries to switch its ID card with second pepper, then the second pepper tries to switch its ID card with the third pepper and so on until the end of the line. Two peppers will switch their ID cards if the pepper that has a larger number on the ID card it’s currently holding wants to become a filled pepper, and the one with the smaller number doesn’t. The peppers will not switch ID cards if they have equal numbers on them.

Your task is to determine the number of peppers that will have their life purpose completed.

입력

The first line of input contains two integers N and X (1 <= N, X <= 1 000) from the task.
Each of the following N lines contains two integers a (1 <= a <= 1 000) and b (0 <= b <= 1) that describe the peppers in the order which they’re waiting in line to be filled. The number a is printed on the ID card of a pepper and represents its age in days, and number b represents it’s life purpose (0 if pepper wants to be served fresh or 1 if it wants to be served as a filled pepper).

출력

The first and only line of output must contain the number of peppers that will have their life purpose completed.

입출력 예

입력

4 5
2 0
3 0
4 0
5 0

출력

0

입력

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

출력

5

입력

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

출력

4
Clarification of the first example: All peppers are young enough, but not a single one of them wants to be
stuffed.
Clarification of the second example: Every two adjacent peppers switched their ID cards.

출처:coci 2013-2014 contest6 1/6
요약: baji072

[질/답] [제출 현황] [푼 후(0)]

[ 채 점 ] [홈으로] [뒤 로]