Monocarp 是一群 $$$n$$$ 学生的导师。他通过流行的信使会议与他们进行交流。
今天对 Monocarp 来说是忙碌的一天——他被要求转发很多帖子和公告给他的小组,这就是为什么他必须在会议上写大量的消息。 Monocarp 非常了解他所辅导的小组中的学生,因此他知道每个学生应该阅读哪条消息:Monocarp 希望学生 $$$i$$$ 阅读消息 $$$m_i$$$。
当然,没有人会阅读会议中的所有消息。这就是 Monocarp 决定固定其中一些的原因。 Monocarp 可以固定任意数量的消息,如果他想让任何人阅读某些消息,他应该固定它 - 否则肯定会被所有人跳过。
不幸的是,即使消息被固定,有些学生也可能会跳过它。对于每个学生 $$$i$$$,Monocarp 知道他们最多会阅读 $$$k_i$$$ 消息。假设 Monocarp 固定 $$$t$$$ 消息;如果 $$$t \le k_i$$$,则第 $$$i$$$ 学生将阅读所有固定消息;但如果 $$$t > k_i$$$,第 $$$i$$$ 个学生将准确选择 $$$k_i$$$ 随机固定消息(大小为 $$$k_i$$$ 的固定消息的所有可能子集都是等概率的)并仅读取所选消息。
Monocarp 希望最大化阅读各自消息的学生的预期数量(即学生 $$$i$$$ 阅读消息 $$$m_i$$$ 的索引 $$$i$$$ 的数量)。帮助他选择应该固定多少(以及哪些)消息!
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 会议中的学生人数。
然后是 $$$n$$$ 行。第 $$$i$$$ 行包含两个整数 $$$m_i$$$ 和 $$$k_i$$$ ($$$1 \le m_i \le 2 \cdot 10^5$$$; $$$1 \le k_i \le 20$$$) — Monocarp 希望第 $$$i$$$ 学生阅读的消息索引以及最大消息数第 $$$i$$$ 个学生将分别阅读。
输出
在第一行中,打印一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — Monocarp 应固定的消息数。在第二行中,打印 $$$t$$$ 不同的整数 $$$c_1$$$, $$$c_2$$$, ..., $$$c_t$$$ ($$$1 \le c_i \le 2 \cdot 10^5$$$) — Monocarp 应固定的消息索引。消息可以按任何顺序列出。
如果有多个答案,请打印其中任何一个。
示例
输入 #1
3 10 1 10 2 5 2
输出 #1
2 5 10
输入 #2
3 10 1 5 2 10 1
输出 #2
1 10
输入 #3
4 1 1 2 2 3 3 4 4
输出 #3
3 2 3 4
输入#4
3 13 2 42 2 37 2
输出#4
3 42 13 37
注意
让我们考虑一下该声明中的示例。
1. 在第一个示例中,Monocarp 固定消息 $$$5$$$ 和 $$$10$$$。 如果第一个学生阅读消息 $$$5$$$,第二个学生阅读消息 $$$5$$$ 和 $$$10$$$,第三个学生阅读消息 $$$5$$$ 和 $$$10$$$,则已阅读各自消息的学生人数将为 $$$2$$$; 如果第一个学生阅读消息 $$$10$$$,第二个学生阅读消息 $$$5$$$ 和 $$$10$$$,第三个学生阅读消息 $$$5$$$ 和 $$$10$$$,则已阅读各自消息的学生人数将为 $$$3$$$。因此,预计将阅读各自消息的学生人数为 $$$\frac{5}{2}$$$。
2. 在第二个示例中,Monocarp 固定消息 $$$10$$$。 如果第一个学生阅读消息 $$$10$$$,第二个学生阅读消息 $$$10$$$,第三个学生阅读消息 $$$10$$$,则已阅读各自消息的学生人数将为 $$$2$$$。因此,预计将阅读各自消息的学生人数为 $$$2$$$。如果 Monocarp 固定了 $$$5$$$ 和 $$$10$$$ 两条消息,则阅读各自消息的学生的预期数量也将是 $$$2$$$。
3. 在第三个示例中,预计将阅读各自消息的学生人数为 $$$\frac{8}{3}$$$。
4. 在第四个示例中,预计将阅读各自消息的学生人数为 $$$2$$$。