Problem Description

Chef Marin is going to cook with $n$ peppers.

He decides to use all peppers whose age is at most $x$ days to make dish A, and use all the other peppers to make dish B.

Each pepper has its own dream: it knows whether it wants to become A or B.

But they do not know the value of $x$. In order to maximize the number of peppers whose dreams come true, they will perform swaps using the following strategy:

• Pepper 1 compares ages with pepper 2, then pepper 2 compares ages with pepper 3, and so on, until pepper $n-1$ compares ages with pepper $n$.
• If the two peppers currently being compared have indices $i, j$, and the pepper with the larger current age wants to become dish A, and the pepper with the smaller current age wants to become dish B, then they swap their ages. $^{[1]}$

Compute the number of peppers whose dreams come true after doing this.

Input Format

The first line contains two integers $n, x$.

The next $n$ lines each contain two integers $a_i, b_i$, representing the age and dream of the $i$-th pepper.

• If $b_i=1$, it means the $i$-th pepper wants to become dish A.
• If $b_i=0$, it means the $i$-th pepper wants to become dish B.

With this definition, a more precise statement of $^\textbf{[1]}$ in the “Description” is:
Two peppers $i, j$ swap their ages if and only if $a_i>a_j$ and $b_i=1$ and $b_j=0$.

Output Format

Output one integer on a single line: the number of peppers whose dreams come true.

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

Hint

Explanation for Sample 1

No pepper wants to become dish A.

Explanation for Sample 2

Every pair of peppers swapped their ages.

Constraints

For $100\%$ of the testdata, $1\le n,x,a_i\le 10^3$, and $b_i\in\{0,1\}$.

Notes

According to the original settings, the full score is 50 points.

Translated from COCI 2014-2015 Contest #6 Task A PAPRIKA。

Translated by ChatGPT 5