# include<bits/stdc++.h> using namespace std ; int V , N , w [101] [1001] , f [101] [1001] , stone [111] [1001] , K ; int main ( ) { cin >> V >> N ; for( int i = 1 ; i <= N ; i ++ ) { int a , b , c ; cin >> a >> b >> c ; stone [c] [++ stone [c] [0]] = a ; w [c] [stone [c] [0]] = b ; K = max ( K , c ) ; } for ( int k = 1 ; k <= K ; k ++ ) { for ( int i = 0 ; i <= stone [k] [0] ; i ++ ) { for ( int j = V ; j >= stone [k] [i] ; j -- ) { f [k] [j] = max ( f [k - 1] [j] , max ( f [k - 1] [j - stone [k] [i]] + w [k] [i] , f [k] [j] ) ) ; } } } cout << f [K] [V] ; return 0 ; }