#include <bits/stdc++.h>
using namespace std;
int m, n;
struct node
{
	int sum=0;
	int a[1001][2] = {0};//0为重量，1为价值
} a[101];//统计每一个组旗下的所有物品
int max1;
int dp[1001][1001];
int zero = 0;
void DP(vector<int> m0, vector<int> v0, int n, int n1)//n表示总的组数，n1表示当前组的序号
{
	if (n1 == n+1)
	{
		memset(dp, 0, sizeof(dp));//先清理为0
		if (zero != 1)
		{
		for(int i=1;i<=n;i++)
			for (int j = 1;j <= m;j++)//这里的开头要用1，而不是从首次能放下这个物品的空间开始
			{
				dp[i][j] = dp[i - 1][j];
				if (j >= m0[i])
					dp[i][j] = max(dp[i][j], dp[i - 1][j - m0[i]] + v0[i]);
			}
		}
		else
		{
			for (int i = 0;i <= n;i++)
				for (int j = 1;j <= m;j++)//这里的开头要用1，而不是从首次能放下这个物品的空间开始
				{
					dp[i][j] = dp[i - 1][j];
					if (j >= m0[i])
						dp[i][j] = max(dp[i][j], dp[i - 1][j - m0[i]] + v0[i]);
				}
		}

		max1 = max(max1, dp[n][m]);
		return;
	}
	for (int i = 1;i <= a[n1].sum;i++)//枚举当前组的所有可能
	{
		vector<int> m1 = m0;
		vector<int> v1 = v0;
		m1.push_back(a[n1].a[i][0]);
		v1.push_back(a[n1].a[i][1]);
		DP(m1, v1, n, n1 + 1);
	}
}
int main()
{
	cin >> m >> n;
	int x1 = 0;
	for (int i = 1;i <= n;i++)
	{
		int x, y, z;//x为重量，y为价值，z为组数
		cin >> x >> y >> z;
		if (x > m)continue;
		if (z == 0)zero = 1;
		a[z].a[++a[z].sum][0] = x;
		a[z].a[a[z].sum][1] = y;
		x1 = max(x1, z);//统计组数
	}
	if (m == 0)
	{
		cout << 0;
		return 0;
	}
	vector<int> m0,v0;
	m0.push_back(0);
	v0.push_back(0);
	if(zero==0)
	DP(m0,v0, x1, 1);
	else 
		DP(m0, v0, x1, 0);
	cout << max1;
}