#include <bits/stdc++.h>
using namespace std;
long long k, n, m;
long long read() {
  char x = getchar();
  long long ans = 0;
  while (!isdigit(x)) x = getchar();
  while (isdigit(x)) ans = ans * 10 + x - '0', x = getchar();
  return ans;
}
long long a[100005];
pair<long long, long long> tong[100005];
struct node {
  long long i, b, id;
  bool operator<(node x) const { return b > x.b; }
} q[100005];
struct Double {
  long long a, b, id;
  bool operator<(Double x) const {
    return (__int128)a * x.b < (__int128)b * x.a;
  }
};
bool cmp(long long x, long long y) { return q[x].id < q[y].id; }
priority_queue<Double> s;
vector<node> V[3];
priority_queue<pair<long long, long long> > Q[100005];
signed main() {
  k = read(), n = read(), m = read();
  for (long long i = 1; i <= k; i++) a[i] = read();
  for (long long i = 1; i <= n; i++) {
    long long opt = read() - 1, pos = read(), b = read();
    V[opt].push_back(node{pos, b, i});
    q[i] = node{pos, b, opt};
  }
  sort(V[2].begin(), V[2].end());
  for (long long i = 0; i < V[0].size(); i++)
    if (tong[V[0][i].i].first < V[0][i].b - a[V[0][i].i])
      tong[V[0][i].i] = make_pair(V[0][i].b - a[V[0][i].i], V[0][i].id);
  for (long long i = 1; i <= k; i++) {
    if (!tong[i].second) continue;
    Q[i].push(tong[i]);
  }
  for (long long i = 0; i < V[1].size(); i++)
    Q[V[1][i].i].push(make_pair(V[1][i].b, V[1][i].id));
  for (long long i = 1; i <= k; i++) {
    if (Q[i].empty()) continue;
    pair<long long, long long> tmp = Q[i].top();
    s.push(Double{tmp.first + a[i], a[i], i});
  }
  vector<long long> ans;
  long long flag = 0;
  for (long long i = 1; i <= m - (long long)V[2].size(); i++) {
    if (s.empty()) {
      for (long long j = 0; j < min((long long)V[2].size(), m - i + 1); j++)
        ans.push_back(V[2][j].id);
      flag = 1;
      break;
    }
    Double now = s.top();
    s.pop();
    long long id = now.id;
    pair<long long, long long> tmp = Q[id].top();
    Q[id].pop();
    ans.push_back(tmp.second);
    a[id] += tmp.first;
    if (Q[id].empty()) continue;
    s.push(Double{Q[id].top().first + a[id], a[id], id});
  }
  if (flag) {
    cout << ans.size() << endl;
    sort(ans.begin(), ans.end(), cmp);
    for (long long i = 0; i < ans.size(); i++) cout << ans[i] << ' ';
    return 0;
  }
  for (long long i = max(1ll, m - (long long)V[2].size() + 1); i <= m; i++) {
    if (s.empty()) {
      for (; i <= m; i++) ans.push_back(V[2][m - i].id);
      break;
    }
    Double now = s.top();
    s.pop();
    long long aa = now.a, b = now.b, id = now.id;
    if (aa < (__int128)b * V[2][m - i].b) {
      for (; i <= m; i++) {
        ans.push_back(V[2][m - i].id);
      }
      break;
    }
    pair<long long, long long> tmp = Q[id].top();
    Q[id].pop();
    ans.push_back(tmp.second);
    a[id] += tmp.first;
    if (Q[id].empty()) continue;
    s.push(Double{a[id] + Q[id].top().first, a[id], id});
  }
  cout << ans.size() << endl;
  sort(ans.begin(), ans.end(), cmp);
  for (long long i = 0; i < ans.size(); i++) cout << ans[i] << ' ';
}
