#include <iostream>
using namespace std;
int
n, sigmat, ans[10001], score, costt;
void
__read__()
{
cin >> sigmat >> n;
}
void
__dp__()
{
for( int i = 1; i <= n; i++ )
{
cin >> score >> costt;
for( int j = costt; j <= sigmat; j++ )
if( ans[j - costt] + score > ans[j] )
ans[j] = ans[j - costt] + score;
}
}
void
__outp__()
{
cout << ans[sigmat] << endl;
}
int
main()
{
__read__();
__dp__();
__outp__();
return 0;
}