[ZJOI2019]浙江省选

题目描述

九条可怜是一个喜欢出题的女孩子,这道题是一道有关浙江省选的硬核模拟题。 在 $9102$ 年,有 $n$ 名选手参加了浙江省选,其中第 $i$ 个选手的智力是 $a_i$,训练量是 $b_i$。作为 出题人,可怜可以自由选择这套题的风格是比较偏套路还是比较偏智力。举例来说,$\mathrm{ZJOI}2018$ 的题就比较偏智力,今年的题就比较偏套路。 为了定量衡量一套题的风格,可怜定义了反向选拔指数 $x$,$x$ 是一个**非负整数**。第 $i$ 个选手在反向选拔指数为 $x$ 的题目上的表现为 $a_ix+b_i$。在 $x$ 给定的情况下,第 $i$ 个人的排名为表现严格大于 $a_ix+bi$ 的人数再加一。 在 $9102$ 年浙江省队的人数为 $m$,因此只有排名小于等于 $m$ 的人才能够进入浙江省队。注意当有并列的情况时,进入浙江省队的人数可能多于 $m$。 不难发现,选手的排名和 $x$ 的关系非常大。现在,可怜想让你计算,第 $i$ 个选手有没有可能进入浙江省队,如果有可能,他最好的排名是多少。

输入输出格式

输入格式


第一行输入两个整数 $n,m(m\leq n)$,表示选手总数以及浙江省队的人数。 接下来 $n$ 行每行两个整数 $a_i,b_i$,表示每个选手的属性值。

输出格式


输出一行 $n$ 个整数,如果第 $i$ 个选手进不了浙江省队,就输出 $-1$,否则输出他可能的最好排名。

输入输出样例

输入样例 #1

3 1
1 5
5 1
2 2

输出样例 #1

1 1 -1

说明

## 样例 1 解释 当 $x=1$ 时,三个人的表现分别为 $6,6,4$,这时前两个人并列第一名,都能进入省队,而第三个人排名第三,没法进入省队。 当 $x>1$ 时,第二个人的表现严格好于第三个人,而当 $x=0$ 时,第一个人的表现严格好于第三个人,因此第三个人无论 $x$ 怎么取,他都没有办法进入省队。 ## 数据范围与约定 | 测试点 | $n$ | $m$ | 测试点 | $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$ | 对于 $100\%$ 的数据,$1\leq a_i \leq 10^9$,$1\leq b_i \leq 10^{18}$,$1\leq m \leq n$。 对于 $100\%$ 的数据,保证选手的属性两两不同,即 $ \forall 1\leq i < j \leq n$,有 $a_i\neq a_j$ 或 $b_i\neq b_j$。