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