#include<iostream>

#include<stdio.h>

#include<string.h>

#include<queue>

#include<algorithm>

using namespace std;

int d[][];    //d[i][j]  i件中，j重量的物品 ，价格最高

int v[],w[];

int Max(int a,int b)

{

    if(a>b)    return a;

    else    return b;

}

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        int n,m;

        cin>>n>>m;

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

            cin>>v[i]>>w[i];

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

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

                d[i][j] = ;

        int maxnum = -;

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

        {

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

            {

                if(j-v[i]>=)

                    d[i][j] = Max(d[i-][j],d[i-][j-v[i]]+v[i]*w[i]);

                else

                    d[i][j] = d[i-][j];

                if(d[i][j] > maxnum)

                    maxnum = d[i][j];

            }

        }

        cout<<maxnum<<endl;

    }

    return ;

}