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