#include<stdio.h>

 #include<string.h>

 #include<algorithm>

 //#include<iostream>

 using namespace std;

 int n,m;

 #define maxn 311

 int f[maxn][maxn],a[maxn],b[maxn],sa[maxn],sb[maxn];

 const int inf=0x3f3f3f3f;

 int main()

 {

     scanf("%d%d",&m,&n);sa[]=sb[]=;

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

     {

         scanf("%d%d",&a[i],&b[i]);

         sa[i]=sa[i-]+a[i];

         sb[i]=sb[i-]+b[i];

     }

     for (int i=;i<=n;i++) if (sa[i]<=m && sb[i]<=m) f[][i]=;else f[][i]=inf;

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

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

         {

             f[i][j]=inf;int tmp=sa[j]-sa[i-];

             if (tmp<=m && sb[j]-sb[i-]<=m) for (int k=;k<i;k++)

             {

                 if (sb[i-]-sb[k-]+tmp>m)

                 f[i][j]=min(f[i][j],f[k][i-]+);

                 else f[i][j]=min(f[i][j],f[k][i-]+);

             }

         }

     int ans=inf;

     for (int i=;i<=n;i++) ans=min(ans,f[i][n]);

     printf("%d\n",ans);

     return ;

 }