Problem M: 买东西

Problem M: 买东西

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

A同学去买东西,有k类物品,每类物品的个数为ai,A同学对每一个物品有一个喜欢度为vj,因为A同学资金紧张,每类物品只能最多选择一样买,可以不买,现在需要你计算有多少种方案,能够使最终购买的物品的总的喜欢度大于m

Input

多组输入
第一行输入两个整数分别为k(k<=6),m(1<=m<=100)
接下来的k行,每行的第一个整数为ai(1<=ai<=100),表示这类物品的数量,接下来的ai个数,第j个为vj(1<=vj<=100),表示A对第j个物品的喜欢度

Output

满足条件下能够获得的最大满意度

Sample Input Copy

2 8
3 1 3 4
4 2 3 4 5
2 5
2 1 6
3 4 5 6

Sample Output Copy

1
7