# include <bits/stdc++.h> using namespace std ; int dp [10001] ; int main ( ) { int m , n ; cin >> m >> n ; for ( int i = i ; i <= n ; i ++ ) { int w , c ; cin >> w > c ; for ( int j = m ; j >= w ; j -- ) { dp [j] = max ( dp [j - w] + c , dp [j] ) ; } } cout << dp [m] << endl ; return 0 ; }