#include <bits/stdc++.h>
using namespace std;
const int INF = (int)(2e9 + 1);
int n, m, k;
vector<pair<int, int>> g[4];
pair<int, vector<int>> getSumWithPath(int common) {
  int time = 0;
  vector<int> path;
  for (int i = 0; i < common; ++i) {
    time += g[3][i].first;
    path.push_back(g[3][i].second);
  }
  if (common + min((int)g[1].size(), (int)g[2].size()) < k) {
    return make_pair(INF, vector<int>());
  }
  int ii;
  for (ii = 0; ii < max(0, k - common); ++ii) {
    time += (g[1][ii].first + g[2][ii].first);
    path.push_back(g[1][ii].second);
    path.push_back(g[2][ii].second);
  }
  if ((int)path.size() > m) {
    return make_pair(INF, vector<int>());
  }
  int a = ii;
  int b = ii;
  int c = common;
  int d = 0;
  int size = (int)path.size();
  for (int i = 0; i < m - size; ++i) {
    pair<int, int> p1 = a == (int)g[1].size() ? make_pair(INF, INF) : g[1][a];
    pair<int, int> p2 = b == (int)g[2].size() ? make_pair(INF, INF) : g[2][b];
    pair<int, int> p3 = c == (int)g[3].size() ? make_pair(INF, INF) : g[3][c];
    pair<int, int> p4 = d == (int)g[0].size() ? make_pair(INF, INF) : g[0][d];
    int mval = min(min(p1.first, p2.first), min(p3.first, p4.first));
    if (mval == INF) {
      return make_pair(INF, vector<int>());
    }
    time += mval;
    if (mval == p1.first) {
      path.push_back(p1.second);
      ++a;
    } else if (mval == p2.first) {
      path.push_back(p2.second);
      ++b;
    } else if (mval == p3.first) {
      path.push_back(p3.second);
      ++c;
    } else if (mval == p4.first) {
      path.push_back(p4.second);
      ++d;
    }
  }
  return make_pair(time, path);
}
int main(int argc, const char* argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m >> k;
  for (int i = 0; i < n; ++i) {
    int t, a, b;
    cin >> t >> a >> b;
    g[(a << a) ^ b].emplace_back(make_pair(t, i));
  }
  for (int i = 0; i < 4; ++i) {
    sort(g[i].begin(), g[i].end(), [](pair<int, int>& p1, pair<int, int>& p2) {
      return p1.first <= p2.first;
    });
  }
  if ((int)g[3].size() + (int)g[1].size() < k ||
      (int)g[3].size() + (int)g[2].size() < k) {
    cout << -1 << endl;
    return 0;
  }
  int time = INF;
  vector<int> path;
  int l = 0, r = (int)g[3].size();
  while (r - l >= 3) {
    int m1 = l + (r - l) / 3;
    int m2 = r - (r - l) / 3;
    pair<int, vector<int>> pm1 = getSumWithPath(m1);
    pair<int, vector<int>> pm2 = getSumWithPath(m2);
    if (pm1.first < pm2.first) {
      r = m2;
    } else {
      l = m1;
    }
  }
  while (l <= r) {
    pair<int, vector<int>> current = getSumWithPath(l);
    if (current.first < time) {
      time = current.first;
      path = current.second;
    }
    ++l;
  }
  if (time == INF) {
    cout << -1 << endl;
    return 0;
  }
  assert((int)path.size() == m);
  cout << time << endl;
  for (int i = 0; i < (int)path.size(); cout << path[i] + 1 << " ", ++i)
    ;
  return 0;
}
