P5328 [ZJOI2019] Zhejiang NOI Qualifier

Kyuukawa Karen is a girl who likes to create problems. This problem is a hardcore simulation problem about the Zhejiang NOI Qualifier. In the year $9102$, there are $n$ contestants participating in the Zhejiang NOI Qualifier. The $i$-th contestant has intelligence $a_i$ and training amount $b_i$. As the problem setter, Karen can freely choose whether this set of problems is more “pattern-based” or more “intelligence-based”. For example, the problems in ZJOI 2018 were more intelligence-based, while this year’s problems are more pattern-based. To measure the style of a set of problems quantitatively, Karen defines the reverse selection index $x$, where $x$ is a **non-negative integer**. The performance of the $i$-th contestant on problems with reverse selection index $x$ is $a_ix+b_i$. When $x$ is fixed, the rank of the $i$-th person is the number of people whose performance is strictly greater than $a_ix+b_i$, plus one. In the year $9102$, the size of the Zhejiang provincial team is $m$, so only those with rank $\le m$ can enter the team. Note that when there are ties, the number of people who enter the team may be greater than $m$. It is not hard to see that a contestant’s rank depends heavily on $x$. Now, Karen wants you to compute whether the $i$-th contestant can possibly enter the Zhejiang provincial team. If possible, what is their best possible rank.

The first line contains two integers $n,m(m\leq n)$, representing the total number of contestants and the size of the Zhejiang provincial team. The next $n$ lines each contain two integers $a_i,b_i$, representing each contestant’s attributes.

Output one line with $n$ integers. If the $i$-th contestant cannot enter the Zhejiang provincial team, output $-1$. Otherwise, output their best possible rank.

# Constraints ## Explanation of Sample 1 When $x=1$, the three contestants’ performances are $6,6,4$. At this time, the first two contestants are tied for 1st place, and both can enter the provincial team. The third contestant ranks 3rd and cannot enter. When $x>1$, the second contestant’s performance is strictly better than the third contestant’s. When $x=0$, the first contestant’s performance is strictly better than the third contestant’s. Therefore, no matter how $x$ is chosen, the third contestant has no way to enter the provincial team. ## Constraints and Notes | Test Point | $n$ | $m$ | Test Point | $n$ | $m$ | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $\le 200$ | $\le 20$ | $6$ | $\le 2\times 10^4$ | $\le 20$ | | $2$ | $\le 200$ | $\le 20$ | $7$ | $\le 2\times 10^4$ | $\le 20$ | | $3$ | $\le 10^5$ | $=1$ | $8$ | $\le 10^5$ | $\le 20$ | | $4$ | $\le 10^5$ | $\le 2$ | $9$ | $\le 10^5$ | $\le 20$ | | $5$ | $\le 10^5$ | $\le 2$ | $10$ | $\le 10^5$ | $\le 20$ | For $100\%$ of the data, $1\leq a_i \leq 10^9$, $1\leq b_i \leq 10^{18}$, and $1\leq m \leq n$. For $100\%$ of the data, it is guaranteed that all contestants’ attributes are pairwise different, i.e., $ \forall 1\leq i < j \leq n$, we have $a_i\neq a_j$ or $b_i\neq b_j$. Translated by ChatGPT 5