E2. Reading Books (hard version)

#include <bits/stdc++.h>
using namespace std;
#define S second
#define F first

typedef long long ll;
typedef pair<int, int> ii;


vector<ii> Both ,Al ,Bob ,Zero;
int n ,m ,k ,Ans;
vector<int> ans;

void Exit() {
    printf("-1");
    exit(0);
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);

    for(int i=0 ; i<n ; i++) {
        int t ,a ,b;
        scanf("%d%d%d" ,&t ,&a ,&b);

        if( a && b )        Both.push_back({t, i});
        else if( !a && b )  Bob.push_back( {t, i});
        else if( a && !b )  Al.push_back ( {t, i});
        else                Zero.push_back({t, i});
    }

    sort(Zero.begin(), Zero.end());
    sort(Both.begin(),Both.end());
    sort(Bob.begin(),Bob.end());
    sort(Al.begin(),Al.end());

    int idBoth = 0,idAl = 0,idBob = 0,idz = 0;
    int szBoth = Both.size() ,szAl = Al.size(),
        szBob = Bob.size()   ,szZ = Zero.size();

    int kAl = k,kBo = k;
    while( m > 0 )
    {
            if( kAl > 0 && kBo > 0 )
            {
                    if( idAl < szAl && idBob < szBob && idBoth < szBoth )
                    {
                            if( Both[idBoth].F >= Al[idAl].F + Bob[idBob].F && m >= 2)
                            {
                                    Ans += Al[idAl].F + Bob[idBob].F;
                                    ans.push_back( Al[idAl++].S );
                                    ans.push_back( Bob[idBob++].S );
                                    kAl --,kBo --, k--, m -= 2;
                            }
                            else
                            {
                                    Ans += Both[idBoth].F;
                                    ans.push_back( Both[idBoth++].S );
                                    kAl --,kBo --, k--, m -= 1;
                            }
                    }
                    else if( idBoth == szBoth && (idAl == szAl || idBob == szBob) )
                            Exit();
                    else if( idBob == szBob || idAl == szAl )
                    {
                            Ans += Both[idBoth].F;
                            ans.push_back( Both[idBoth++].S );
                            kAl --,kBo --, k--, m -= 1;
                    }
                    else if( idBoth == szBoth && m >= 2 )
                    {
                            Ans += Al[idAl].F + Bob[idBob].F;
                            ans.push_back( Al[idAl++].S );
                            ans.push_back( Bob[idBob++].S );
                            kAl --,kBo --, k--, m -= 2;
                    }
                    else Exit();
            }
            else
            {
                    vector<ii> all;
                    for(int i = idBoth ; i < szBoth ; i++)
                        all.push_back( Both[i] );
                    for(int i = idAl ; i < szAl ; i++)
                        all.push_back( Al[i] );
                    for(int i = idBob ; i < szBob ; i++)
                        all.push_back( Bob[i] );
                    for(int i = idz ; i < szZ ; i++)
                        all.push_back( Zero[i] );

                    sort(all.begin() ,all.end());
                    k = -1;
                    kAl = -1 ;
                    kBo = -1 ;
                    for(int i=0 ; i < (int)all.size() && m > 0 ; i++ ,m--){
                            Ans += all[i].F;
                            ans.push_back( all[i].S );
                    }
                    if( m > 0 ) Exit();
            }
    }

    if( max( kAl ,kBo ) <= 0 && m <= 0 ){
        printf("%d\n",Ans);
        for(auto i : ans)
            printf("%d ",i + 1);
    } else Exit();

    return 0;
}