小C与小B的切磋

小C很喜欢玩一款著名的卡牌游戏“炉石传说”。
该游戏基本规则是，你有一些手牌，每回合你有若干数量的法力水晶，然后每张牌有其打出需要花费的水晶数量。
你可以在本回合的法力水晶数量限制下，打出若干张手牌。
最近该游戏又更新了新版本，推出了新职业恶魔猎手，其职业特色为“流放”。
小C跃跃欲试，拿起一套恶魔猎手的套牌在新版本的第二天光速上了传说（炉石传说中天梯最高等级）。
然而还没等小C激动多少时间，恶魔猎手第二天就被削弱了。（削得好！确实太强）

小C决定不打天梯了，和好友小B进行切磋。当前回合，小C现在有 $n$张手牌，其中有一部分是“流放”牌，一部分是普通牌。
不论是哪种牌打出都需要水晶数量$w_i$。每张“流放”牌都有其价值$v_i$，每张普通牌的价值都为0。
但是，“流放”牌只有在手牌的最左边或者最右边打出才会体现其价值$v_i$，否则其价值为0。
现在小C有$m$个法力水晶，小C需要按一定顺序打出若干张牌，并且总花费水晶不超过$m$的情况下，使得获得的总价值尽可能大。
请你帮帮他计算出可以获得的最大价值。

第一行一个整数 $T$ ($T \leq 20$) ，表示数据组数。
对于每一组数据：
第 $1$ 行两个正整数 $n,m$，分别表示小C的手牌数量、当前回合法力水晶数量。
接下来 $n$ 行，按从左到右的顺序描述n张牌的信息。
每行数据描述一张手牌的信息。每行首先给出两个整数 $w_i,u_i$，分别表示该手牌的打出需要花费的法力水晶数量和该牌是否
为“流放”牌。$u_i=1$表示是“流放”牌，$u_i=0$则不是。若是“流放”牌，则该行再给出一个整数$v_i$，表示该张“流放”牌的价值。

数据范围保证：$ 1 \leq n \leq 200000,1 \leq m \leq 10^9 ,1 \leq w_i,v_i \leq 10000 $

对于每组数据，输出一个整数表示小C当前回合可以获得的最大价值。

2
5 3
1 1 5
1 0
1 0
1 1 10
1 0
5 2
1 1 5
1 0
1 0
1 1 10
1 0

15
10

杭州电子科技大学计算机学院Debug杯程序设计竞赛