#include <iostream>#include<cstring> using namespace std;int dp[30001];int main(){    int num;    cin>>num;    int a,b;    int n,m;    while(num--)    {            memset(dp,0,sizeof(dp));            cin>>n>>m;                            for(int i=1;i<=m;i++)            {                cin>>a>>b;                for(int j=n;j>=a;j--)                    dp[j] = max(dp[j],dp[j-a]+a*b);             }        cout<<dp[n]<<endl;    }    return 0;}