#include<iostream>
#include<algorithm>
using namespace std;
int n, m, q;
const int N = 1010, M = 1010;
int w[N], v[N], num[N];
int f[N], F[N][3];

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> w[i] >> v[i] >> num[i];
	}
	for (int i = 1; i <= m; i++)
	{
		bool b = 1;
		if (F[num[i]][1] != 0) b = 0;
		for (int j = n; j >= 0; j--)
		{

			if (j >= w[i])
			{
				if(b == 0)
				{
					int a = f[j];
					f[j] = max(f[j], f[j - w[i] + F[num[i]][1]] + v[i] - F[num[i]][2]);
					if (f[j] != a)
					{
						F[num[i]][1] = w[i];
						F[num[i]][2] = v[i];
					}

				}
				else
				{
					int a = f[j];
					f[j] = max(f[j], f[j - w[i]] + v[i]);
					if (f[j] != a)
					{
						F[num[i]][1] = w[i];
						F[num[i]][2] = v[i];
					}
				}

			}
		}
	}
	cout << f[n];
}