#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

int s[2000][2],dp[150],t[150][3];

int main()

{

	int text;

	scanf("%d",&text);

	while(text--)

	{

		int n,m;

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

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

		scanf("%d %d %d",&t[i][0],&t[i][1],&t[i][2]);

		int cnt=0;

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

		{

			int k=1;

			while(t[i][2]-k>0)

			{

				s[cnt][0]=k*t[i][0];

				s[cnt++][1]=k*t[i][1];

				t[i][2]-=k;

				k*=2;

			}

			s[cnt][0]=t[i][2]*t[i][0];

			s[cnt++][1]=t[i][2]*t[i][1];

		}

		memset(dp,0,sizeof(dp));

		for(int i=0;i<cnt;i++)

		{

			for(int j=n;j>=s[i][0];j--)

			if(dp[j]<dp[j-s[i][0]]+s[i][1])

			dp[j]=dp[j-s[i][0]]+s[i][1];

		}

		printf("%d\n",dp[n]);

	}

	return 0;

}