#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std ;

struct node

{

    int n;

    int d ;

} cas[] ;

int main()

{

    int cash ;

    int n,ch[] ;

    while(scanf("%d",&cash)!=EOF)

    {

        int m;

        cin>>n ;

        for(int i =  ; i < n ; i++)

            cin>>cas[i].n >>cas[i].d ;

        memset(ch,,sizeof(ch)) ;

        ch[] =  ;

        /*ch是标记数组，也可以说是一个小小的优化吧，

        再已经标记的基础上继续往上加，不用再从头开始加了,否则会超时*/

        int maxm =  ;

        //for循环从每种纸币开始，再对钱数进行枚举，每种纸币又有n张

        for(int i =  ; i < n ; i++)

            for(int j = maxm ; j >=  ; j--)

               if(ch[j])

                    for(int k =  ; k <= cas[i].n ; k++)

                    {

                        m = j + cas[i].d * k;

                        if(m > cash)

                            break ;

                        ch[m] =  ;

                        if(m > maxm)

                            maxm = m ;

                    }

        cout<<maxm<<endl ;

    }

    return  ;

}