#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAXN = 60;
const int MAXV = 3200;

int n, V;

struct Tree {
	Tree *children, *next;
	int c, w;
	int f[MAXV + 1];

	Tree() {}
	Tree(Tree *parent, int c, int w) : next(parent->children), c(c), w(w) {
		memset(f, 0, sizeof(f));
	}

	void solve() {
		for (int v = V; v >= c; v--) f[v] = w;
		for (Tree *t = children; t; t = t->next) {
			t->solve();
			for (int v = V - c; v >= t->c; v--) {
				for (int i = t->c; i <= std::min(V - c, v + c); i++) {
					f[v + c] = std::max(f[v + c], f[v + c - i] + t->f[i]);
				}
			}
		}
	}
} trees[MAXN + 1];

inline void addTree(int id, int parent, int c, int w) {
	trees[parent].children = new (&trees[id]) Tree(&trees[parent], c, w);
}

int main() {
	freopen("budget.in", "r", stdin);
	freopen("budget.out", "w", stdout);

	scanf("%d %d", &V, &n);
	V /= 10;

	for (int i = 0; i < n; i++) {
		int c, p, q;
		scanf("%d %d %d", &c, &p, &q);

		addTree(i + 1, q, c / 10, c * p);
	}

	trees[0].solve();

	printf("%d\n", trees[0].f[V]);

	fclose(stdin);
	fclose(stdout);

	return 0;
}