Reading Books (hard version)
Contest: Codeforces Round 653 (Div. 3)
Difficulty rating: 2500
Tags: data structures, greedy, implementation, sortings, ternary search, two pointers

Easy and hard versions are actually different problems, so read statements of both problems completely and carefully.

Summer vacation has started so Alice and Bob want to play and joy, but... Their mom doesn't think so. She says that they have to read exactly $$$m$$$ books before all entertainments. Alice and Bob will read each book together to end this exercise faster.

There are $$$n$$$ books in the family library. The $$$i$$$-th book is described by three integers: $$$t_i$$$ — the amount of time Alice and Bob need to spend to read it, $$$a_i$$$ (equals $$$1$$$ if Alice likes the $$$i$$$-th book and $$$0$$$ if not), and $$$b_i$$$ (equals $$$1$$$ if Bob likes the $$$i$$$-th book and $$$0$$$ if not).

So they need to choose exactly $$$m$$$ books from the given $$$n$$$ books in such a way that:

- Alice likes at least $$$k$$$ books from the chosen set and Bob likes at least $$$k$$$ books from the chosen set;
- the total reading time of these $$$m$$$ books is minimized (they are children and want to play and joy as soon a possible).

The set they choose is the same for both Alice an Bob (it's shared between them) and they read all books together, so the total reading time is the sum of $$$t_i$$$ over all books that are in the chosen set.

Your task is to help them and find any suitable set of books or determine that it is impossible to find such a set.

Input format:
The first line of the input contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le k \le m \le n \le 2 \cdot 10^5$$$).

The next $$$n$$$ lines contain descriptions of books, one description per line: the $$$i$$$-th line contains three integers $$$t_i$$$, $$$a_i$$$ and $$$b_i$$$ ($$$1 \le t_i \le 10^4$$$, $$$0 \le a_i, b_i \le 1$$$), where:

- $$$t_i$$$ — the amount of time required for reading the $$$i$$$-th book;
- $$$a_i$$$ equals $$$1$$$ if Alice likes the $$$i$$$-th book and $$$0$$$ otherwise;
- $$$b_i$$$ equals $$$1$$$ if Bob likes the $$$i$$$-th book and $$$0$$$ otherwise.

Output format:
If there is no solution, print only one integer -1.

If the solution exists, print $$$T$$$ in the first line — the minimum total reading time of the suitable set of books. In the second line print $$$m$$$ distinct integers from $$$1$$$ to $$$n$$$ in any order — indices of books which are in the set you found.

If there are several answers, print any of them.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
6 3 1
6 0 0
11 1 0
9 0 1
21 1 1
10 1 0
8 0 1

Example output:
24
6 5 1

Example input:
6 3 2
6 0 0
11 1 0
9 0 1
21 1 1
10 1 0
8 0 1

Example output:
39
4 6 5

Editorial:
A little explanation: this editorial will be based on the easy version editorial so I'll use some definitions from it.
Here we go, the most beautiful problem of the contest is waiting us.
Well, the key idea of this problem almost the same with the easy version idea. Let's iterate over the number of elements in 11-group, we need to take the cheapest ones again. If the number of elements we take from 11-group is $$$cnt$$$ then we need to take $$$k-cnt$$$ elements from 01 and 10-groups. But one more thing: let's iterate over $$$cnt$$$ not from zero but from the smallest possible number which can give us any correct set of books (the numeric value of the answer doesn't matter) $$$start$$$. The value of $$$start$$$ can be calculated using $$$k, m$$$ and sizes of groups by formula or even simple loop. If we can't find any suitable value of $$$start$$$, the answer is -1.
Let's call $$$cnt$$$ elements from 11-group and $$$k-cnt$$$ elements from 01 and 10-groups we take necessary. Other elements of the whole set of books are free (but elements of 11-group are not free). Let's create the set $$$fr$$$ which contains all free elements (and fill it beforehand). So, now we took some necessary elements, but we need to take some free elements to complete our set. Let's create the other set $$$st$$$ which contains free elements we take to the answer (and maintain the variable $$$sum$$$ describing the sum of elements of $$$st$$$). How do we recalculate $$$st$$$? Before the start of the first iteration our set $$$fr$$$ is already filled with some elements, let's update $$$st$$$ using them.
Update is such an operation (function) that tosses the elements between $$$fr$$$ and $$$st$$$. It will do the following things (repeatedly, and stop when it cannot do anything):
• While the size of $$$st$$$ is greater than needed (so we take more than $$$m$$$ books in total), let's remove the most expensive element from $$$st$$$ and add it to $$$fr$$$;
• while the size of $$$st$$$ is less than needed (so we take less than $$$m$$$ books in total), let's remove the cheapest element from $$$fr$$$ and add it to $$$st$$$;
• while the cheapest element from $$$fr$$$ is cheaper than the most expensive element form $$$st$$$, let's swap them.
Note that during updates you need to recalculate $$$sum$$$ as well.
So, we go over all possible values $$$cnt$$$, updating $$$st$$$ before the first iteration and after each iteration. The size of both sets changes pretty smooth: if we go from $$$cnt$$$ to $$$cnt+1$$$, we need to remove at most one element from $$$st$$$ (because we take one element from 11-group during each iteration) and we need to add at most two elements to $$$st$$$ and $$$fr$$$ (because we remove at most two elements from 01 and 10-groups during one iteration).
To restore the answer, let's save such a value $$$cnt$$$ that the answer is minimum with this value $$$cnt$$$ (let it be $$$pos$$$). Then let's just run the same simulation once more from the beginning but stop when we reach $$$pos$$$. Then $$$st$$$ will contain free elements we need to take to the answer, $$$pos$$$ describes the number of elements we need to take from 11-group and $$$k-pos$$$ describes which elements from 01 and 01-groups we need to take.
Of course, there are some really tough technical things like case-handling (there is a lot of cases, for example, the size of $$$st$$$ can be negative at some moment and you need to carefully handle that, and $$$k-cnt$$$ can be negative after some number of iterations and there are other cases because of that, and so on).
Time complexity: $$$O(n \log{n})$$$.