# include <bits/stdc++.h> using namespace std ; int tme [10001] , vle [10001] , dp [10001] [10001] ; int main ( ) { int t , m ; cin >> t >> m ; for ( int i = 1 ; i <= m ; i ++ ) { cin >> tme [i] >> vle [i] ; } for ( int i = 1 ; i <= m ; i ++ ) { for ( int j = 0 ; j <= t ; j ++ ) { dp [i] [j] = dp [i - 1] [j] ; if ( ( j >= tme [i] ) && ( dp [i] [j] < dp [i - 1] [j - tme [i]] + vle [i] ) ) { dp [i] [j] = dp [i - 1] [j - tme [i]] + vle [i] ; } } } cout << dp [m] [t] << endl ; return 0 ; }