#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() {
ll s,n; cin>>s>>n;
vt<ll> v(n), w(n), k(n);
for (int i=0;i<n;i++){
cin>>v[i]>>w[i]>>k[i];
k[i] = min(k[i], s/w[i]);
}
vt<ll> dp(s+1, 0);
for (int i=0;i<n;i++){
for (int cn=1;cn<=k[i];cn++){
for (int x=s;x>=w[i];x--){
dp[x] = max(dp[x], dp[x-w[i]]+v[i]);
}
}
}
cout << dp[s] << endl;
}
int main() {
int tt=1;
cin>>tt;
while(tt--) solve();
return 0;
}
