#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int k, n, m;
int a[N];
struct nod {
  int ty, x, y;
} b[N];
vector<int> e[N][3];
int cmp(int x, int y) { return b[x].y > b[y].y; }
struct P {
  long long x, y;
  P(long long _x = 0, long long _y = 0) { x = _x, y = _y; }
};
bool operator<(P a, P b) {
  if (a.y == 0) return 0;
  if (b.y == 0) return 1;
  return (long double)a.x / a.y < (long double)b.x / b.y;
}
P c[N];
int d[N], d0;
int cmpd(int x, int y) { return c[y] < c[x]; }
int cmd2(int x, int y) { return b[x].ty < b[y].ty; }
int main() {
  scanf("%d %d %d", &k, &n, &m);
  for (int i = 1, B = k; i <= B; i++) scanf("%d", &a[i]);
  for (int i = 1, B = n; i <= B; i++) {
    scanf("%d %d %d", &b[i].ty, &b[i].x, &b[i].y);
    b[i].ty--;
    e[b[i].x][b[i].ty].push_back(i);
  }
  for (int i = 1, B = k; i <= B; i++) {
    for (int j = 0, B = 2; j <= B; j++)
      sort(e[i][j].begin(), e[i][j].end(), cmp);
    if (e[i][0].size() && b[e[i][0][0]].y > a[i])
      b[e[i][0][0]].y -= a[i], e[i][1].push_back(e[i][0][0]);
    sort(e[i][1].begin(), e[i][1].end(), cmp);
    int n1 = e[i][1].size(), n2 = e[i][2].size();
    int l = 0, r = 0;
    long long s1 = a[i];
    for (int j = 1, B = n1 + n2; j <= B; j++) {
      long long s2 = l == n1 ? 0 : s1 + b[e[i][1][l]].y;
      long long v = r == n2 ? 0 : b[e[i][2][r]].y;
      if (l == n1 || (r < n2 && P(s2, s1) < P(v, 1))) {
        c[e[i][2][r]] = P(v, 1);
        d[++d0] = e[i][2][r];
        r++;
        continue;
      }
      c[e[i][1][l]] = P(s2, s1);
      d[++d0] = e[i][1][l];
      l++;
      s1 = s2;
    }
  }
  sort(d + 1, d + d0 + 1, cmpd);
  m = min(d0, m);
  sort(d + 1, d + m + 1, cmd2);
  printf("%d\n", m);
  for (int i = 1, B = m; i <= B; i++) printf("%d ", d[i]);
}
