#include <iostream> using namespace std; int n, m; int v[30], w[30]; int f[30005]; int main() { cin >> n >> m; for ( int i = 1; i <= m; ++ i ) { cin >> w[i] >> v[i]; v[i] *= w[i]; } for ( int i = 1 ; i <= m ; ++ i ) { for ( int j = n ; j >= w[i] ; -- j ) { f[j] = max(f[j], f[j - w[i]] + v[i]); } } cout << f[n] << endl; return 0; }