P7954 [COCI 2014/2015 #6] PAPRIKA

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.

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 one integer on a single line: the number of peppers whose dreams come true.

#### 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](https://hsin.hr/coci/archive/2014_2015/)** [Contest #6](https://hsin.hr/coci/archive/2014_2015/contest6_tasks.pdf) Task A _**PAPRIKA**_。 Translated by ChatGPT 5