#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=;

const ll INF=1LL<<;

ll a[N],b[N],f[N][N][][],j,k,n,m,tot1,tot2;

int main()

{

    scanf("%d%d",&m,&n);

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

     {

           scanf("%d%d",&k,&j);

        if (j)a[++tot1]=k;

        else b[++tot2]=k;

     }

    sort(a+,a++tot1); sort(b+,b++tot2);

    for (int i=tot1+;i<=n;i++)a[i]=INF;

    for (int i=tot2+;i<=n;i++)b[i]=INF;

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

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

      for (int t=;t<=;t++)

       for (int l=;l<=;l++)f[i][j][t][l]=INF;

    f[][][][]=;

    int ad,bd;

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

     {

        for (int j=,ad=a[j]*(m-i+),bd=b[i-j]*(m-i+);j<=i;j++,

        ad=a[j]*(m-i+),bd=b[i-j]*(m-i+))

         {

             f[i][j][][]=min(f[i-][j-][][],

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

             f[i][j][][]=f[i-][j-][][]+ad;

            f[i][j][][]=min(f[i-][j][][],

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

             f[i][j][][]=f[i-][j][][]+bd;

         }

        bd=b[i]*(m-i+);

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

        f[i][][][]=f[i-][][][]+bd;

     }

    ll ans=INF;

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

     {

         ans=min(ans,f[m][i][][]);

        ans=min(ans,f[m][i][][]);

         ans=min(ans,f[m][i][][]);

         ans=min(ans,f[m][i][][]);

         ans=min(ans,f[m][i][][]);

     }

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

    return ;

}