题目内容

塔子哥是一位电脑发烧友，热爱DIY组装电脑。他研究了各种零部件，了解到不同型号的零件有不同的性能和价格，而性价比也会有所差异。因此，他需要谨慎地选择零部件，以使他的电脑既具有出色的性能，又不会让他花费太多的钱。

这一次，塔子哥决定升级他的电脑，需要购买$n$个零件，每个零件有多个型号可供选择。他知道每个型号的价格 $a_i$ 和性能 $v_i$ ，并且他有一个限制条件，塔子哥需要每个零件选择一个型号并且总价格不能超过$x$元。他希望在这个限制条件下，选出的零件能够使他的电脑性能尽可能强大。塔子哥需要你的帮助，来找到最优的选择方案。

输入描述

第一行输入两个正整数 $n$ 和 $x$ ，代表电脑的零件数量以及塔子哥最大的预算。

接下来的 $3*n$ 行，每三行用来描述一个零件的不同型号的价格和性能。

对于每种零件，第一行输入一个正数 $m$ ，代表该零件有多少种型号；

第二行输入 $m$ 个整数，代表这 $m$ 个零件的价格；

第三行输入 $m$ 个整数，代表这 $m$ 个零件的性能。

$1 \leq n,m \leq 40$

$1 \leq a_{i},v_{i},x \leq 10^9$

保证所有 $m$ 之和不超过 $40$ ，即所有零件的型号数量之和不超过 $40$ 种。

输出描述

如果无法完成组装，则直接输出$-1。$ 否则输出一个正整数，代表最终最大的性能。

样例$1$

输入

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

输出

4

说明： 一共需要两个零件。 第一个零件选择第一个型号，第二个零件也选择第一个型号。 这样总价格为 $3$ ，总性能为 $4$ 。