Бобёр Борис Луговой продаёт квартиры по очень выгодной (для него) цене. Помогите ему заработать как можно больше за $$$t$$$ дней!
Есть $$$n$$$ квартир, квартиры пронумерованы от $$$1$$$ до $$$n$$$ в порядке задания во входных данных. Квартира $$$i$$$ имеет стоимость $$$a_i$$$ и находится в районе $$$b_i$$$.
Дни продаж пронумерованы от $$$1$$$ до $$$t$$$. В каждый день Борис может:
Каждый раз при продаже Борис утверждает, что в квартире жил только он последние несколько лет (этот аргумент помогает продать квартиру дороже), поэтому в одном районе за $$$K$$$ подряд идущих дней он может продать не больше одной квартиры (иначе жители этого района заметили бы что у Бориса несколько квартир).
В первой строке записаны три целых числа $$$n$$$, $$$K$$$, $$$t$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le K \le 10^5$$$, $$$1 \le t \le 10^5$$$).
В следующих $$$n$$$ строках записаны пары целых чисел $$$a_i$$$, $$$b_i$$$ ($$$0 \le a_i \le 10^9$$$, $$$1 \le b_i \le n$$$) — стоимость квартиры и номер района, в котором она находится.
В первой строке выведите одно целое число — максимальную возможную выручку Бориса за $$$t$$$ дней.
Во второй строке выведите $$$t$$$ целых чисел. $$$d$$$-е число должно быть равно номеру квартиры, проданной в день $$$d$$$, или $$$-1$$$, если в этот день Борис не продаёт квартиру.
Если существует несколько оптимальных ответов, выведите любой.
| Группа | Баллы | Дополнительные ограничения | Необходимые группы |
| 1 | 7 | $$$k = 1$$$ | – |
| 2 | 19 | $$$k = t$$$ | – |
| 3 | 17 | Все $$$a_i$$$ равны | – |
| 4 | 17 | Все $$$b_i$$$ равны | – |
| 5 | 40 | – | 1, 2, 3 |
6 2 410 115 18 214 314 314 3
53 5 1 6 2
6 3 810 110 110 120 220 220 2
90 4 1 -1 5 2 -1 6 3