/*
多重背包，用2进制的拆分思想，转化为01背包
*/
#include<cstdio>
#include<cstring>
#define maxn 99999
#define max(a,b) (a)>(b)?(a):(b)
int dp[maxn],c[maxn],v[maxn];
int main()
{
int Z,V,m,i,a,b,x,j;
scanf("%d",&Z);
while(Z--)
{
scanf("%d%d",&V,&m);
int cnt=1;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&x);
int t=1;
while(x>=t)
{
v[cnt]=a*t;
c[cnt++]=b*t;
x-=t;
t<<1;
}
if(x)
{
v[cnt]=a*x;
c[cnt++]=b*x;
}
}
memset(dp,0,sizeof(dp));
for(i=1;i<cnt;i++)
for(j=V;j>=v[i];j--)
dp[j]=max(dp[j],dp[j-v[i]]+c[i]);
printf("%d\n",dp[V]);
}
return 0;
}
/*
完全背包
转化为可重复的01背包
*/
#include<cstdio>
#include<cstring>
#define max(a,b) (a)>(b)?(a):(b)
#define maxn 100010
int dp[100010];
int main()
{
int n,i,j,V;
int c[200],v[200];
while(scanf("%d",&n)!=EOF)
{
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
scanf("%d%d",&c[i],&v[i]);
scanf("%d",&V);
for(i=1;i<=n;i++)
for(j=v[i];j<=V;j++)
dp[j]=max(dp[j],dp[j-v[i]]+c[i]);
printf("%d\n",dp[V]);
}
return 0;
}
/*
二维费用背包
变形较多。三重循环较难掌握。
*/
#include<cstdio>
#include<cstring>
#define maxn 150
#define max(a,b) (a)>(b)?(a):(b)
int main()
{
int c[maxn],v[maxn],dp[maxn][maxn];
int ex,pa,ki,mm,i,j,k;
while(scanf("%d%d%d%d",&ex,&pa,&ki,&mm)!=EOF)//experience,patience,kinds,mostmonserts
{
int f=1;
memset(dp,0,sizeof(dp));
for(i=1;i<=ki;i++)
scanf("%d%d",&c[i],&v[i]);
for(i=1;i<=ki;i++)
for(j=v[i];j<=pa;j++)
for(k=1;k<=mm;k++)
dp[j][k]=max(dp[j][k],dp[j-v[i]][k-1]+c[i]);
for(i=1;i<=pa;i++)
for(k=1;k<=mm;k++)
if(dp[i][k]>=ex)
{
f=0;
printf("%d\n",pa-i);
goto A;
}
if(f)
printf("-1\n");
A:;
}
return 0;
}