import java.io.*;
import java.util.*;
public class knapsack
{
public static void main(String[] args) throws IOException
{
FastReader infile = new FastReader();
int s = infile.nextInt();
int n = infile.nextInt();
int[][] items = new int[n+1][3]; //price weight copies
for(int x = 1; x <= n; x++){
items[x][0] = infile.nextInt();
items[x][1] = infile.nextInt();
items[x][2] = infile.nextInt();
}
int[][] dp = new int[n+1][s+1];
for(int x = 0; x <= n; x++){
Arrays.fill(dp[x],-1);
}
dp[0][0] = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j <= s; j++){
if(dp[i][j] == -1)
continue;
int price = items[i+1][0];
int weight = items[i+1][1];
int copies = items[i+1][2];
int limiter = Math.min((int)(s-j)/weight,copies);
for(int x = 0; x <= limiter; x++){
dp[i+1][j+x*weight] = Math.max(dp[i+1][j+x*weight],dp[i][j]+price*x);
}
}
}
int solution = 0;
for(int x = 0; x <= s; x++){
solution = Math.max(dp[n][x],solution);
}
System.out.print(solution);
}
}
class FastReader
{
BufferedReader br;
StringTokenizer st;
public FastReader() throws FileNotFoundException
{
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String file) throws FileNotFoundException
{
br = new BufferedReader(new FileReader(file));
}
boolean hasNext()
{
while (st == null || !st.hasMoreElements())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (Exception e)
{
return false;
}
}
return true;
}
String next()
{
while (st == null || !st.hasMoreElements())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt()
{
return Integer.parseInt(next());
}
long nextLong()
{
return Long.parseLong(next());
}
double nextDouble()
{
return Double.parseDouble(next());
}
String nextLine()
{
String str = "";
try
{
str = br.readLine();
}
catch (IOException e)
{
e.printStackTrace();
}
return str;
}
}
