Простая и сложная версии на самом деле являются разными задачами, поэтому прочитайте условия обеих задач полностью и внимательно.
Летние каникулы начались, поэтому Алиса и Боб хотят играть и веселиться, но... Их мама не согласна с этим. Она говорит, что они должны прочитать ровно \(m\) книг перед всеми развлечениями. Алиса и Боб прочитают каждую книгу вместе, чтобы быстрее закончить это задание.
В семейной библиотеке есть \(n\) книг. \(i\)-я книга характеризуется тремя целыми числами: \(t_i\) — количество времени, которое Алиса и Боб должны потратить, чтобы прочитать ее, \(a_i\) (равное \(1\), если Алисе нравится \(i\)-я книга, и \(0\), если не нравится), и \(b_i\) (равное \(1\), если Бобу нравится \(i\)-я книга, и \(0\), если не нравится).
Поэтому им нужно выбрать ровно \(m\) книг из имеющихся \(n\) книг таким образом, что:
- Алисе нравятся не менее \(k\) книг из выбранного множества и Бобу нравятся не менее \(k\) книг из выбранного множества;
- общее время, затраченное на прочтение этих \(m\) книг минимизировано (ведь они дети и хотят начать играть и веселиться как можно скорее).
Множество, которое они выбирают, одинаковое и для Алисы и для Боба (они читают одни и те же книги), и они читают все книги вместе, таким образом, суммарное время чтения равно сумме \(t_i\) по всем книгам, которые находятся в выбранном множестве.
Ваша задача — помочь им и найти любое подходящее множество книг или определить, что такое множество найти невозможно.
Выходные данные
Если подходящего решения не существует, выведите целое число -1.
Если решение существует, выведите \(T\) первой строкой — минимальное суммарное время, необходимое для прочтения подходящего множества книг. Второй строкой выведите \(m\) различных целых чисел от \(1\) до \(n\) в любом порядке — индексы книг, включенных в выбранное вами множество.
Если существует несколько подходящих ответов, вы можете вывести любой из них.