小明是个有钱人每次约会都会精心准备礼物，由于小明太有钱了完全不在乎钱的问题只要东西越贵越好但是小明也不能带太多礼物毕竟出去约会带一车东西也不太合适。于是小明想让你帮忙计算一下他最多能带的礼物的最大价值。
商店里有N种礼物，每种礼物的数量为C1，C2......Cn，每种礼物的体积为W1，W2......Wn（Wi为整数），与之相对应的价值为P1,P2......Pn（Pi为整数），小明最多想带体积不超过W的礼物。

第一行一个t表示总共需要的组数，
每组数据2个整数n，w。n表示礼物种类，w表示小明能带的最大体积（1<=n<=100,1<=w<=50000）
然后n行，每行3个整数，wi,pi,ci表示礼物的体积，价值，数量。(1<=wi,pi<=10000,1<=ci<=200)

输出可以容纳的最大价值。