选择困难症
题号:NC13594
时间限制:C/C++/Rust/Pascal 3秒,其他语言6秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

小L有严重的选择困难症。
早上起床后,需要花很长时间决定今天穿什么出门。
假设一共有k类物品需要搭配选择,每类物品的个数为Ai,每个物品有一个喜欢值Vj,代表小L对这件物品的喜欢程度。
小L想知道,有多少种方案,使得选出来的总喜欢值>M
需要注意,每类物品,至多选择1件,可以不选。

输入描述:

多组输入
每组数据第一行输入k M(k<=6,1<=M<=1e8),表示有多少类物品
接下来k行,每行以Ai(1<=Ai<=100)开头,表示这类物品有多少个,接下来Ai个数,第j个为Vj(1<=Vj<=1e8),表示小L对这类物品的第j个的喜欢值是多少。

输出描述:

每组输出一行,表示方案数
示例1

输入

复制
2 5
3 1 3 4
2 2 3
2 1
2 2 2
2 2 2

输出

复制
3
8