#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define vt vector
#define pb push_back
#define F first
#define S second
void solve() {
int s,n; cin>>s>>n;
vt<vt<ll>> item(s+1);
for (int i=0;i<n;i++){
int v,w,k; cin>>v>>w>>k;
k = min(k, s/w);
for (int j=0;j<k;j++) item[w].pb(v);
}
vt<ll> dp(s+1, 0);
for (int w=1;w<=s;w++){
sort(all(item[w]), greater<>());
vt<ll> values;
int cn = min(sz(item[w]), (s+w-1)/w);
for (int i=0;i<cn;i++) values.pb(item[w][i]);
for (int v: values){
for (int x=s;x>=w;x--){
dp[x] = max(dp[x], dp[x-w]+v);
}
}
}
cout << dp[s] << endl;
}
int main() {
int tt=1;
cin>>tt;
while(tt--) solve();
return 0;
}
