public class Main
{
public static void main(String[] args) {
java.util.Scanner in = new java.util.Scanner(System.in);
int w, n;
int NegNum = -1;
w = in.nextInt();
n = in.nextInt();
int WeiCos[][], s[];
WeiCos = new int [n][2];
s = new int [w + 1];
for(int i = 0; i < n; i++){
for(int j = 0; j < 2; j++){
WeiCos[i][j] = in.nextInt();
}
}
s[0] = 0;
for(int j = 1; j <= w; j++){
s[j] = NegNum;
}
for(int i = 0; i < n; i++){
for(int j = WeiCos[i][0]; j <= w; j++){
if(s[j - WeiCos[i][0]] != NegNum && s[j] < s[j - WeiCos[i][0]] + WeiCos[i][1]){
s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];
}
}
}
int maxS = 0;
for(int i = 1; i <= w; i++){
maxS = Math.max(maxS, s[i]);
}
System.out.print(maxS);
}
}