Ученые планируют набор продуктов для экспедиции на Марс. Планируется, что запас экспедиции будет состоять из $$$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|} Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 5 | $$$n = 1$$$, $$$1 \leq c, t_i \leq 10^9$$$, $$$1 \leq k_i \leq 10^{18}$$$ | полные | |
| 2 | 22 | $$$1 \leq n \leq 16$$$, $$$1 \leq c, t_i \leq 10^9$$$, $$$1 \leq k_i \leq 10^{18}$$$ | 1 | полные |
| 3 | 15 | $$$1 \leq n \leq 2000$$$, $$$c = 1$$$, $$$1 \leq t_i \leq 2000$$$, $$$1 \leq k_i \leq 10^{18}$$$ | первая ошибка | |
| 4 | 18 | $$$1 \leq n \leq 2000$$$, $$$1 \leq c, t_i \leq 10^9$$$, $$$1 \leq k_i \leq 10^{18}$$$ | 1, 2, 3 | первая ошибка |
| 5 | 15 | $$$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 | первая ошибка |
| 6 | 25 | $$$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
