Монокарп — тьютор группы из $$$n$$$ студентов. Он связывается с ними через конференцию в популярном мессенджере.
Сегодня у Монокарпа был напряженный день — его просили переслать его группе огромное количество объявлений, поэтому ему пришлось написать в конференции очень много сообщений. Монокарп достаточно хорошо знает студентов из группы, поэтому понимает, какое сообщение является важным для каждого студента: Монокарп хочет, чтобы студент $$$i$$$ прочитал сообщение $$$m_i$$$.
Конечно же, никто не будет читать все сообщения. Поэтому Монокарп решил прикрепить некоторые из них. Монокарп может прикрепить любое количество сообщений, и если он хочет, чтобы какое-то сообщение было прочитано, ему стоит прикрепить его — в противном случае никто такое сообщение не прочитает.
К сожалению, даже если сообщение прикреплено, некоторые студенты все равно могут его пропустить. Для каждого студента $$$i$$$ Монокарп знает, что этот студент прочитает не более $$$k_i$$$. Предположим, что Монокарп прикрепляет $$$t$$$ сообщений; если $$$t \le k_i$$$, то $$$i$$$-й студент прочитает все прикрепленные сообщения; но если $$$t > k_i$$$, $$$i$$$-й студент выберет ровно $$$k_i$$$ случайных прикрепленных сообщений (все различные подмножества размера $$$k_i$$$ множества прикрепленных сообщений равновероятны) и прочитает только их.
Монокарп хочет максимизировать математическое ожидание количества студентов, которые прочитают необходимые им сообщения (это соответствует количеству таких индексов $$$i$$$, что студент $$$i$$$ прочитает сообщение $$$m_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$$$) — номер сообщения, которое должен прочитать $$$i$$$-й студент, и максимальное кол-во сообщений, которое $$$i$$$-й студент может прочитать, соответственно.
В первой строке выведите одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — количество сообщений, которые должен прикрепить Монокарп. Во второй строке выведите $$$t$$$ различных целых чисел $$$c_1$$$, $$$c_2$$$, ..., $$$c_t$$$ ($$$1 \le c_i \le 2 \cdot 10^5$$$) — номера сообщений, которые необходимо прикрепить. Номера сообщений можно выводить в любом порядке.
Если оптимальных ответов несколько, выведите любой из них.
3 10 1 10 2 5 2
2 5 10
3 10 1 5 2 10 1
1 10
4 1 1 2 2 3 3 4 4
3 2 3 4
3 13 2 42 2 37 2
3 42 13 37
Рассмотрим примеры из условия.
Поэтому математическое ожидание количества студентов, которые прочитают соответствующие им сообщения, равно $$$\frac{5}{2}$$$.
Поэтому математическое ожидание количества студентов, которые прочитают соответствующие им сообщения, равно $$$2$$$. Если бы Монокарп прикрепил и сообщение $$$5$$$, и сообщение $$$10$$$, математическое ожидание так же было бы равно $$$2$$$.
Название |
---|