#3047. 「ZJOI2019」浙江省选

内存限制:512 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

九条可怜是一个喜欢出题的女孩子,这道题是一道有关浙江省选的硬核模拟题。

在 9102 年,有 n 名选手参加了浙江省选,其中第 i 个选手的智力是 a_i ,训练量是 b_i 。作为出题人,可怜可以自由选择这套题的风格是比较偏套路还是比较偏智力。举例来说,ZJOI2018 的题就比较偏智力,今年的题就比较偏套路。

为了定量衡量一套题的风格,可怜定义了反向选拔指数 x x 是一个非负整数。第 i 个选手在反向选拔指数为 x 的题目上的表现为 a_ix + b_i 。在 x 给定的情况下,第 i 个人的排名为表现严格大于 a_ix + b_i 的人数再加一。

在 9102 年浙江省队的人数为 m ,因此只有排名小于等于 m 的人才能够进入浙江省队。注意当有并列的情况时,进入浙江省队的人数可能多于 m

不难发现,选手的排名和 x 的关系非常大。现在,可怜想让你计算,第 i 个选手有没有可能进入浙江省队,如果有可能,他最好的排名是多少。

输入格式

第一行输入两个整数 n, m ,表示选手总数以及浙江省队的人数。
接下来 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 怎么取,他都没有办法进入省队。

样例 2

见附加文件 zjoi1.in/ans

数据范围与提示

测试点 n m 测试点 n m
1 \le 200 \le 20 6 \le 2\times 10^3 \le 20
2 7
3 \le 10^5 =1 8 \le 10^5
4 \le 2 9
5 10

对于 100\% 的数据, 1 \le a_i \le 10^9, 1 \le b_i \le 10^{18} 1 \le m \le n

对于 100\% 的数据,保证选手的属性两两不同,即 \forall 1 \le i < j \le n ,有 a_i\neq a_j b_i\neq b_j