#include <bits/stdc++.h>

using namespace std;

int n,W,w[],v[],m[],dp[];

int deq[],deqv[]; // 模拟deque deq保存下标 deqv保存值

int main()

{

    int t;

    while(~scanf("%d",&t)) {

        while(t--) {

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

            for(int i=;i<n;i++)

                scanf("%d%d%d",&w[i],&v[i],&m[i]);

            memset(dp,,sizeof(dp));

            for(int i=;i<n;i++) // 第i种物品

                for(int j=;j<w[i];j++) { // 枚举不同余数

                    int head=, tail=;

                    /// 双端队列维护余数为 j 时的最优解

                    // 则每个 j 开始时都应该赋0清空队列

                    for(int k=;k*w[i]+j<=W;k++) { // 枚举该物品个数

                        int nowv=dp[k*w[i]+j]-k*v[i];

                        /// 原本重量为 k*w[i]+j 的最优解

                        // 可能其他种物品有更新过该重量的最优解

                        /// 压到 j 时对应的最优解

                        while(head<tail && deqv[tail-]<=nowv) tail--;

                        /// 与曾中出现过存放在队列中的最优解比较

                        deq[tail]=k, deqv[tail++]=nowv; // 更新队列 队头head对应的即为最优解

                        dp[k*w[i]+j]=deqv[head]+k*v[i]; // 更新dp[]保存的最优解

                        if(deq[head]==k-m[i]) head++;

                        /// 如果head对应的已经是m[i]个中的第一个

                        /// 即到下一个时 head对应的物品数量会超出m[i]的限制

                        /// 则应该舍弃这个最优解 把队头head移向下一位

                    }

                }

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

        }

    }

    return ;

}