include <cstdio>

include <cstring>

class Node {

public:

  Node();
  int v_[3], p_[3];
};
int _max(const int a, const int b);
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  n /= 10;
  Node node[m];
  for (int i = 1; i <= m; ++i) {
    int q;
    scanf("%d %d %d", node[i].v_, node[i].p_, &q);
    node[i].v_[0] /= 10;
    if (q) {
      --m;
      if (node[q].p_[1] == 0) {
        node[q].v_[1] = node[i].v_[0];
        node[q].p_[1] = node[i].p_[0];
      } else {
        node[q].v_[2] = node[i].v_[0];
        node[q].p_[2] = node[i].p_[0];
      }
      --i;
    }
  }
  int dp[n + 1][m + 1];
  memset(dp, 0, sizeof(dp));
  for (int j = 1; j <= m; ++j) {
    for (int i = 0; i <= n; ++i) {
      int rest = i, value = 0;
      dp[i][j] = dp[i][j - 1];
      if (rest >= node[j].v_[0]) {
        rest -= node[j].v_[0];
        value += node[j].v_[0] * node[j].p_[0];
        dp[i][j] = _max(dp[i][j], dp[rest][j - 1] + value);
        if (rest >= node[j].v_[1]) {
          rest -= node[j].v_[1];
          value += node[j].v_[1] * node[j].p_[1];
          dp[i][j] = _max(dp[i][j], dp[rest][j - 1] + value);
          if (rest >= node[j].v_[2]) {
            rest -= node[j].v_[2];
            value += node[j].v_[2] * node[j].p_[2];
            dp[i][j] = _max(dp[i][j], dp[rest][j - 1] + value);
            rest += node[j].v_[2];
            value -= node[j].v_[2] * node[j].p_[2];
          }
          rest += node[j].v_[1];
          value -= node[j].v_[1] * node[j].p_[1];
        }
        if (rest >= node[j].v_[2]) {
          rest -= node[j].v_[2];
          value += node[j].v_[2] * node[j].p_[2];
          dp[i][j] = _max(dp[i][j], dp[rest][j - 1] + value);
        }
      }
    }
  }
  printf("%d\n", dp[n][m] * 10);
  return 0;
}
Node::Node() {
  memset(v_, 0, sizeof(v_));
  memset(p_, 0, sizeof(p_));
}
int _max(const int a, const int b) { return a < b ? b : a; }