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