B. Продажа квартир
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бобёр Борис Луговой продаёт квартиры по очень выгодной (для него) цене. Помогите ему заработать как можно больше за $$$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$$$, если в этот день Борис не продаёт квартиру.

Если существует несколько оптимальных ответов, выведите любой.

Система оценки
ГруппаБаллы Дополнительные ограничения Необходимые группы
17$$$k = 1$$$–
219$$$k = t$$$–
317Все $$$a_i$$$ равны–
417Все $$$b_i$$$ равны–
540–1, 2, 3
Примеры
Входные данные
6 2 4
10 1
15 1
8 2
14 3
14 3
14 3
Выходные данные
53
5 1 6 2 
Входные данные
6 3 8
10 1
10 1
10 1
20 2
20 2
20 2
Выходные данные
90
4 1 -1 5 2 -1 6 3