P5961 [BalticOI 2006] coin collector Coin Collector.

In a country, there are $n$ types of coins in circulation, including a 1-cent coin. In addition, there is a banknote of value $K$ cents, which is larger than the value of any coin. A coin collector wants to collect one sample of every coin value. He already has some coins at home, but now he only takes a single $K$-cent banknote to a shop. The shop sells a total of $K-1$ items, priced at $1$ cent, $2$ cents, ..., $K-1$ cents. The shop gives change using the following algorithm: 1. Suppose the total change needed is $A$ cents. 2. Find the largest coin value not exceeding $A$, and let it be a $B$-cent coin. 3. Give the customer one $B$-cent coin, then set $A$ to $A-B$. 4. If $A=0$, the algorithm ends; otherwise, go to step 2. The collector wants to buy one item using his $K$-cent banknote. Please write a program to compute: how many types of coins that he does not yet have can the collector obtain? Under the condition of maximizing the previous answer, what is the most expensive item he can buy?

The first line contains two integers $n$ and $K$. The next $n$ lines describe the values of the coins in circulation and whether they have already been collected. Line $i+1$ contains an integer $C_i\ (1\le C_i

The first line outputs one integer, the maximum number of coin types that the collector can obtain that he did not have before. The second line outputs one integer, under the condition in the previous question, the price of the most expensive item the collector can buy.

For all data, $1\le n\le 5\times 10^5$, $2\le K\le 10^9$. Translated by ChatGPT 5