#include? < iostream >

using ? namespace ?std;

#define ?N?100001

int ?nk[ 11 ],?dk[ 11 ],?n,?m,?ans[N],?num[N];

int ?main(){
???? while (?scanf( " %d%d " , & m, & n?) != ?EOF?){
???????? for (? int ?i = ? 0 ;?i < ?n;? ++ i?)?scanf( " %d%d " ,?nk + ?i,?dk + ?i?);
???????? for (? int ?i = ? 0 ;?i <= ?m;? ++ i?)?ans[i] = ? 0 ;?ans[ 0 ] = ? 1 ;
????????
???????? for (? int ?i = ? 0 ;?i < ?n;? ++ i?){
???????????? for (? int ?j = ? 0 ;?j <= ?m;? ++ j?)?num[j] = ? 0 ;
????????????
???????????? for (? int ?j = ?dk[i];?j <= ?m;? ++ j?)
???????????? if (? ! ?ans[j]? && ?ans[j - dk[i]]? && ?num[j - ?dk[i]] < ?nk[i]?){
????????????????num[j] = ?num[j - dk[i]] + ? 1 ;
????????????????ans[j] = ? 1 ;?}
????????}
????????
???????? int ?res = ?m;
???????? while (?ans[res] == ? 0 ? && ?res >= ? 1 ?)?res -- ;
????????printf( " %d\n " ,?res?);
????}
????
???? return ? 0 ;
}