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