#include <iostream>
using namespace std;
int
cost[3][61], pref[3][61], n, smoney, ans[3201];
void
__read__()
{
cin >> smoney >> n;
smoney /= 10;
for( int i = 1; i <= n; i++ )
{
int
x, y, z;
cin >> x >> y >> z;
if( z != 0 )
if( cost[1][z] == 0 )
{
cost[1][z] = x / 10;
pref[1][z] = y;
}
else
{
cost[2][z] = x / 10;
pref[2][z] = y;
}
else
{
cost[z][i] = x / 10;
pref[z][i] = y;
}
}
}
void
__dp__()
{
for( int i = 1; i <= n; i++ )
for( int j = smoney; j > 0; j-- )
{
if( j >= cost[0][i] )
if( ans[j] < ans[j - cost[0][i]] + pref[0][i] * cost[0][i] )
ans[j] = ans[j - cost[0][i]] + pref[0][i] * cost[0][i];
if( j >= cost[0][i] + cost[1][i] )
if( ans[j] < ans[j - cost[0][i] - cost[1][i]] + pref[0][i] * cost[0][i] + pref[1][i] * cost[1][i] )
ans[j] = ans[j - cost[0][i] - cost[1][i]] + pref[0][i] * cost[0][i] + pref[1][i] * cost[1][i];
if( j >= cost[0][i] + cost[2][i] )
if( ans[j] < ans[j - cost[0][i] - cost[2][i]] + pref[0][i] * cost[0][i] + pref[2][i] * cost[2][i] )
ans[j] = ans[j - cost[0][i] - cost[2][i]] + pref[0][i] * cost[0][i] + pref[2][i] * cost[2][i];
if( j >= cost[0][i] + cost[1][i] + cost[2][i] )
if( ans[j] < ans[j - cost[0][i] - cost[1][i] - cost[2][i]] + pref[0][i] * cost[0][i] + pref[1][i] * cost[1][i] + pref[2][i] * cost[2][i] )
ans[j] = ans[j - cost[0][i] - cost[1][i] - cost[2][i]] + pref[0][i] * cost[0][i] + pref[1][i] * cost[1][i] + pref[2][i] * cost[2][i];
}
}
void
__outp__()
{
cout << ans[smoney] * 10 << endl;
}
int
main()
{
__read__();
__dp__();
__outp__();
return 0;
}