题目描述

xinjun是各类手游的狂热粉丝，因随手一氪、一氪上千而威震工大，现在他迷上了阴阳师。xinjun玩手游有一个习惯，就是经过层层计算制定出一套方案来使操作利益最大化(因此即使有扫荡券也不用，故称圣雄肝帝)。已知阴阳师有 $N$ 个模式可以操作，模式 $i$ 有ai种操作，但每种模式每日只能选用一种操作，可以不选。操作 $j$ 能收益vj，但需要花费体力wj点。xinjun每日拥有体力 $M$ 点，求他每日最多能得到多少收益。

输入格式

第一行一个正整数T($T<=10$)，表示共有 $T$ 组数据。

对于每组数据，第一行两个正整数 $N$，M($1<=N$，M<=$1000$)。

接下来 $N$ 段数据，每段第一行一个正整数ai($1<=ai$<=$1000$)，第二行ai个正整数vj($1<=vj$<=$1000$)，第三行ai个正整数wj($1<=wj$<=$1000$)。

每组数据ai之和不大于 $104$。

输出格式

对每组数据输出一行，即xinjun每日最多能得到多少收益。

样例

样例输入 1

1
3 10
2
2 3
3 2
2
1 1
3 4
1
5
5

样例输出 1

9