1374E2 - Reading Books (hard version)
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(nlogn).

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()

#define F_OR(i, a, b, s) for (int i = (a); ((s) > 0 ? i < (b) : i > (b)); i += (s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)

const int mxN=2e5;
int n, k, m;
vector<ar<ll, 2>> v[4];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;
    FOR(n) {
        int t, a, b;
        cin >> t >> a >> b;
        v[a*2+b].push_back({t, i});
    }
    FOR(4) {
        //v[i].push_back(0);
        sort(all(v[i]));
        //FOR(j, 1, sz(v[i]))
            //v[i][j]+=v[i][j-1];
    }
    ll ans=1e18;
    set<int> ans2;
    FOR(_, 2) {
        ll s=0;
        set<int> s2;
        priority_queue<ar<ll, 2>> pq;
        priority_queue<ar<ll, 2>, vector<ar<ll, 2>>, greater<ar<ll, 2>>> pq2;
        FOR(j, 1, 3) {
            FOR(min(k, sz(v[j])))
                s+=v[j][i][0], s2.insert(v[j][i][1]);
            FOR(i, k, sz(v[j])) {
                s+=v[j][i][0], s2.insert(v[j][i][1]);
                pq.push(v[j][i]);
            }
        }
        FOR(sz(v[0])) {
            s+=v[0][i][0], s2.insert(v[0][i][1]);
            pq.push(v[0][i]);
        }
        FOR(sz(v[3])+1) {
            //cout << i << " " << s << endl;
            if(i) {
                s+=v[3][i-1][0], s2.insert(v[3][i-1][1]);
                FOR(j, 1, 3) {
                    if(sz(v[j])>k-i&&k-i>=0)
                        pq.push(v[j][k-i]);
                }
            }
            if(pq2.size()) {
                pq.push(pq2.top());
                s+=pq2.top()[0];
                s2.insert(pq2.top()[1]);
                pq2.pop();
            }
            while(pq.size()&&pq.size()>m-i-2*max(k-i, 0)) {
                s-=pq.top()[0];
                s2.erase(pq.top()[1]);
                pq2.push(pq.top());
                pq.pop();
            }
            if(pq.size()==m-i-2*max(k-i, 0)&&v[3].size()>=i&&sz(v[1])>=k-i&&sz(v[2])>=k-i&&s<ans) {
                ans=s;
                //ans2=s2;
            }
            if(_&&s==ans&&ans2.empty())
                ans2=s2;
        }
    }
    cout << (ans>=1e18?-1:ans) << "\n";
    for(int a : ans2)
        cout << a+1 << " ";
}

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1000000007;
const char nl = '\n';
const int MX = 100001; //check the limits, dummy

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int N, M, K; cin >> N >> M >>  K;
    vpi A[4];
    F0R(i, N) {
        int T, X, Y; cin >> T >> X >> Y;
        if (X && Y) {
            A[0].pb({T, i});
        } else if (X) {
            A[1].pb({T, i});
        } else if (Y) {
            A[2].pb({T, i});
        } else {
            A[3].pb({T, i});
        }
    }

    F0R(i, 4) sort(all(A[i]));
    if (sz(A[0]) + sz(A[1]) < K || sz(A[0]) + sz(A[2]) < K || 2*K - M > sz(A[0])) {
        cout << -1 << nl; return 0;
    }
    int nb = min(K, sz(A[0]));
    ll best = 2e9, sum = 0;
    vi P(4);
    vi bp(4);
    F0R(i, nb) {
        sum += A[0][i].f;
    }
    P[0] = nb;
    F0R(i, K - nb) {
        sum += A[1][i].f;
    }
    P[1] = K - nb;
    F0R(i, K-nb) {
        sum += A[2][i].f;
    }
    P[2] = K - nb;
    P[3] = 0;

    while (P[0] + P[1] + P[2] + P[3] < M) {
        int bv = 1e9, ba = -1;
        F0R(i, 4) {
            if (P[i] == sz(A[i])) continue;
            if (ckmin(bv, A[i][P[i]].f)) {
                ba = i;
            }
        }
        P[ba]++; sum += bv;
    }
    best = sum; bp = P;

    F0Rd(i, nb) {

        P[0]--;
        sum -= A[0][P[0]].f;
        int pos = K - i;
        if (sz(A[1]) < pos || sz(A[2]) < pos || 2*K-i > M) continue;
        while (P[1] < pos) {
            sum += A[1][P[1]].f;
            P[1]++;
        }
        while (P[2] < pos) {
            sum += A[2][P[2]].f;
            P[2]++;
        }
        vi cap = {i, pos, pos, 0};
        while (P[0] + P[1] + P[2] + P[3] > M) {
            int bv = 0, ba = -1;
            F0R(i, 4) {
                if (P[i] == cap[i]) continue;
                if (ckmax(bv, A[i][P[i]-1].f)) {
                    ba = i;
                }
            }
            sum -= bv; P[ba]--;
        }

        while (P[0] + P[1] + P[2] + P[3] < M) {
            int bv = 1e9, ba = -1;
            F0R(i, 4) {
                if (P[i] == sz(A[i])) continue;
                if (ckmin(bv, A[i][P[i]].f)) {
                    ba = i;
                }
            }
            P[ba]++; sum += bv;
        }
        while (true) {
            int lo = 1e9, hi = 0, pl = -1, ph = -1;
            F0R(i, 4) {
                if (P[i] != cap[i] && ckmax(hi, A[i][P[i]-1].f)) {
                    ph = i;
                }
                if (P[i] != sz(A[i]) && ckmin(lo, A[i][P[i]].f)) {
                    pl = i;
                }
            }
            if (lo < hi) {
                sum += hi - lo;
                P[ph]--;
                P[pl]++;
            } else break;
        }

        if (ckmin(best, sum)) {
            bp = P;
        }
    }

    cout << best << nl;

    F0R(i, 4) {
        F0R(j, bp[i]) {
            cout << A[i][j].s + 1 << " ";
        }
    }
    cout << nl;
    return 0;
}

// read the question correctly (ll vs int)
// template by bqi343


#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define IT iterator
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
#define debug puts("wzpakking")
#define y1 ysghysgsygsh
#define all(v) v.begin(),v.end()
using namespace std;
const int N=200005;
int n,m,k;
vector<pii> vec[4];
ll sum[4][N];
int find(int x,int y){
    return lower_bound(vec[x].begin(),vec[x].end(),pii(y,1<<30))-vec[x].begin();
}
void Construct(int &p1,int &p2,int &p3,int &p4){
    if (p1+p2+p3+p4>m) return;
    int l=0,r=10000,ans=0;
    while (l<=r){
        int mid=(l+r)/2;
        int v=max(p1,find(0,mid));
        v+=max(p2,find(1,mid));
        v+=max(p3,find(2,mid));
        v+=max(p4,find(3,mid));
        if (v<=m) ans=mid,l=mid+1;
        else r=mid-1;
    }
    //cout<<ans<<' '<<p1+p2+p3+p4<<' '<<p1<<' '<<p2<<' '<<p3<< '<<p4<<endl;
    p1=max(p1,find(0,ans));
    p2=max(p2,find(1,ans));
    p3=max(p3,find(2,ans));
    p4=max(p4,find(3,ans));
    if (find(0,ans+1)>p1) p1+=min(find(0,ans+1)-p1,m-p1-p2-p3-p4);
    if (find(1,ans+1)>p2) p2+=min(find(1,ans+1)-p2,m-p1-p2-p3-p4);
    if (find(2,ans+1)>p3) p3+=min(find(2,ans+1)-p3,m-p1-p2-p3-p4);
    if (find(3,ans+1)>p4) p4+=min(find(3,ans+1)-p4,m-p1-p2-p3-p4);
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    For(i,1,n){
        int x,a,b;
        scanf("%d%d%d",&x,&a,&b);
        vec[a*2+b].PB(pii(x,i));
    }
    For(i,0,3)
        sort(vec[i].begin(),vec[i].end());
    ll ans=1ll<<60;
    int p0,p1,p2,p3;
    For(i,0,3)
        For(j,1,n){
            sum[i][j]=sum[i][j-1];
            if (j<=vec[i].size())
                sum[i][j]+=vec[i][j-1].fi;
        }
    For(i,0,vec[3].size()) if (i<=k){
        int pp1,pp2,pp3,pp4;
        pp1=0; pp2=pp3=k-i; pp4=i;
        Construct(pp1,pp2,pp3,pp4);
        if (pp2>vec[1].size()||pp3>vec[2].size()||pp4>vec[3].size()) continue;
        if (pp1+pp2+pp3+pp4>m) continue;
        //cout<<i<<' '<<pp1<<' '<<pp2<<' '<<pp3<<' '<<pp4<<endl;
        if (sum[0][pp1]+sum[1][pp2]+sum[2][pp3]+sum[3][pp4]<ans){
            ans=sum[0][pp1]+sum[1][pp2]+sum[2][pp3]+sum[3][pp4];
            p0=pp1; p1=pp2; p2=pp3; p3=pp4;
        }
    }
    //cout<<p0<<' '<<p1<<' '<<p2<<' '<<p3<<endl;
    if (ans==1ll<<60) puts("-1");
    else{
        printf("%lld\n",ans);
        For(i,0,p0-1) printf("%d ",vec[0][i].se);
        For(i,0,p1-1) printf("%d ",vec[1][i].se);
        For(i,0,p2-1) printf("%d ",vec[2][i].se);
        For(i,0,p3-1) printf("%d ",vec[3][i].se);
    }
}