import java.util.;
class Main{
public static void main(String[] args) {
Scanner in =new Scanner(System.in);
int m=in.nextInt();
int n=in.nextInt();
int f[][]=new int [n+1][m+1];
int max=0;
for(int i=1;i<=n;i) {
int v=in.nextInt();
int k=in.nextInt();
for(int j=0;j<=m;j) {
f[i][j]=f[i-1][j];
if(j>=v) {
f[i][j]=Math.max(f[i][j],f[i-1][j-v]+kv);
}
if(max<f[i][j]) {
max=f[i][j];
}
}
}
System.out.println(f[n][m]);
}
}