E2. Чтение книг (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Летние каникулы начались, поэтому Алиса и Боб хотят играть и веселиться, но... Их мама не согласна с этим. Она говорит, что они должны прочитать ровно $$$m$$$ книг перед всеми развлечениями. Алиса и Боб прочитают каждую книгу вместе, чтобы быстрее закончить это задание.

В семейной библиотеке есть $$$n$$$ книг. $$$i$$$-я книга характеризуется тремя целыми числами: $$$t_i$$$ — количество времени, которое Алиса и Боб должны потратить, чтобы прочитать ее, $$$a_i$$$ (равное $$$1$$$, если Алисе нравится $$$i$$$-я книга, и $$$0$$$, если не нравится), и $$$b_i$$$ (равное $$$1$$$, если Бобу нравится $$$i$$$-я книга, и $$$0$$$, если не нравится).

Поэтому им нужно выбрать ровно $$$m$$$ книг из имеющихся $$$n$$$ книг таким образом, что:

  • Алисе нравятся не менее $$$k$$$ книг из выбранного множества и Бобу нравятся не менее $$$k$$$ книг из выбранного множества;
  • общее время, затраченное на прочтение этих $$$m$$$ книг минимизировано (ведь они дети и хотят начать играть и веселиться как можно скорее).

Множество, которое они выбирают, одинаковое и для Алисы и для Боба (они читают одни и те же книги), и они читают все книги вместе, таким образом, суммарное время чтения равно сумме $$$t_i$$$ по всем книгам, которые находятся в выбранном множестве.

Ваша задача — помочь им и найти любое подходящее множество книг или определить, что такое множество найти невозможно.

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

Первая строка теста содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le k \le m \le n \le 2 \cdot 10^5$$$).

Следующие $$$n$$$ строк содержат описания книг, по одному описанию в строке: $$$i$$$-я строка содержит три целых числа $$$t_i$$$, $$$a_i$$$ и $$$b_i$$$ ($$$1 \le t_i \le 10^4$$$, $$$0 \le a_i, b_i \le 1$$$), где:

  • $$$t_i$$$ — количество времени, необходимое для прочтения $$$i$$$-й книги;
  • $$$a_i$$$, равное $$$1$$$, если Алисе нравится $$$i$$$-я книга, и $$$0$$$ в обратном случае;
  • $$$b_i$$$, равное $$$1$$$, если Бобу нравится $$$i$$$-я книга, и $$$0$$$ в обратном случае.
Выходные данные

Если подходящего решения не существует, выведите целое число -1.

Если решение существует, выведите $$$T$$$ первой строкой — минимальное суммарное время, необходимое для прочтения подходящего множества книг. Второй строкой выведите $$$m$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в любом порядке — индексы книг, включенных в выбранное вами множество.

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

Примеры
Входные данные
6 3 1
6 0 0
11 1 0
9 0 1
21 1 1
10 1 0
8 0 1
Выходные данные
24
6 5 1
Входные данные
6 3 2
6 0 0
11 1 0
9 0 1
21 1 1
10 1 0
8 0 1
Выходные данные
39
4 6 5