import java.util.*;
public class knapsack {
public static int [][][] dp ;
public static int solve(int [][] store,int s, int currWt, int idx, int used){
if(idx >= store.length || currWt > s) return Integer.MIN_VALUE ;
if(dp[idx][currWt][used] != -1)return dp[idx][currWt][used] ;
//Pick
int pick1 = 0 ;
if(store[idx][1] + currWt <= s && store[idx][2] > used){
pick1 = store[idx][0] + solve(store, s, currWt+store[idx][1], idx, used+1) ;
}
int notPick = solve(store, s, currWt, idx+1,0) ;
return dp[idx][currWt][used] = Math.max(pick1,notPick) ;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in) ;
int s = sc.nextInt() ;
int n = sc.nextInt() ;
int [][] store = new int [n][3] ;
int maxK = -1 ;
for(int i=0 ;i <n ;i++){
store[i][0] = sc.nextInt() ;
store[i][1] = sc.nextInt() ;
store[i][2] = sc.nextInt() ;
maxK = Math.max(maxK,store[i][2]) ;
}
dp = new int [n][s+1][maxK+1] ;
for(int [][] arr2 : dp){
for(int [] arr3 : arr2){
Arrays.fill(arr3,-1) ;
}
}
System.out.println(solve(store, s, 0, 0,0));
}
}
