C. Продукты в экспедиции
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ученые планируют набор продуктов для экспедиции на Марс. Планируется, что запас экспедиции будет состоять из $$$n$$$ типов продуктов, пронумерованных целыми числами от $$$1$$$ до $$$n$$$. У экспедиции будет $$$k_i$$$ порций продуктов $$$i$$$-го типа. Продукт $$$i$$$-го типа должен быть использован на протяжении $$$t_i$$$ дней после начала экспедиции, после чего портится. Если за $$$t_i$$$ дней не все порции продукты $$$i$$$-го типа съедены, то все оставшиеся порции этого продукта уничтожаются.

В экспедицию планируют направить $$$c$$$ участников. Каждый день участники экспедиции выбирают любые $$$c$$$ имеющихся у них порций и съедают их. Разные участники экспедиции могут есть как одинаковые, так и различные типы продуктов.

Отдел планирования снабжения хочет понять, насколько избыточен набор продуктов, запланированный для экспедиции. Они хотят выяснить, какое максимальное различное количество типов продуктов участники экспедиции смогут полностью съесть в процессе экспедиции, не допустив уничтожения ни одной их порции продукта этого типа.

Требуется написать программу, которая по описанию продуктов и количеству участников экспедиции определяет максимальное количество типов продуктов, которые могут быть полностью съедены в процессе экспедиции.

Входные данные

В первой строке два целых числа $$$n$$$ и $$$c$$$ — количество типов продуктов и количество участников экспедиции ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq c \leq 10^9$$$).

В следующих $$$n$$$ строках находится по два целых числа $$$t_i$$$, $$$k_i$$$ — время, за которое портятся продукты $$$i$$$-го типа, и количество порций продукта $$$i$$$-го типа ($$$1 \leq t_i \leq 10^9$$$, $$$1 \leq k_i \leq 10^{18}$$$).

Выходные данные

Сначала выведите единственное целое число $$$s$$$ ($$$0 \leq s \leq n$$$) — максимальное количество типов продуктов, которые могут быть полностью съедены в процессе экспедиции. В следующей строке выведите $$$s$$$ целых чисел $$$p_1, p_2, \ldots, p_s$$$ ($$$1 \leq p_i \leq n$$$, все $$$p_i$$$ различны) — номера типов продуктов.

Если существует несколько подходящих множеств типов продуктов максимального размера, выведите любое из них. Типы продуктов можно выводить в любом порядке.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

|c|c|}

Подзадача

Баллы Ограничения Необходимые подзадачи Информация о проверке
15 $$$n = 1$$$, $$$1 \leq c, t_i \leq 10^9$$$, $$$1 \leq k_i \leq 10^{18}$$$полные
222$$$1 \leq n \leq 16$$$, $$$1 \leq c, t_i \leq 10^9$$$, $$$1 \leq k_i \leq 10^{18}$$$1полные
315 $$$1 \leq n \leq 2000$$$, $$$c = 1$$$, $$$1 \leq t_i \leq 2000$$$, $$$1 \leq k_i \leq 10^{18}$$$первая ошибка
418$$$1 \leq n \leq 2000$$$, $$$1 \leq c, t_i \leq 10^9$$$, $$$1 \leq k_i \leq 10^{18}$$$1, 2, 3первая ошибка
515 $$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq c, t_i \leq 10^9$$$, $$$1 \leq k_i \leq 10^{18}$$$, все $$$t_i$$$ совпадают1первая ошибка
625 $$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq c, t_i \leq 10^9$$$, $$$1 \leq k_i \leq 10^{18}$$$1 – 5первая ошибка
Примеры
Входные данные
1 1
4 4
Выходные данные
1
1
Входные данные
5 3
3 4
2 6
4 5
3 4
5 7
Выходные данные
3
1 4 5
Входные данные
3 2
2 6
4 9
1 3
Выходные данные
0