雫露露的背包
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述



雫露露的生日快要到了，她的 N 个朋友为她准备了礼物，其中第 i 位朋友准备了 a_i 份礼物，第 j(1 \leq j \leq a_i) 份礼物的空间大小为 b_{i,j}。

为了能够更好地接收朋友们的礼物，雫露露提前准备了一个容量为 W 的背包。但是，为了给朋友们留下好印象，她只会从每位朋友那里收取恰好一份礼物。雫露露打算充分利用背包的空间，她想知道有多少种收取礼物的方式，使背包恰好装满。

其中，定义两种收取礼物的方式不同，当且仅当存在一位朋友，两种方式收取了该位朋友不同的礼物。

输入描述:

第一行输入两个正整数 N,W(1 \leq N,W \leq 3000)，分别表示朋友的个数和背包的容量。

接下来输入 N 行，每位朋友一行数据，先输入一个正整数 a_i(1 \leq a_i \leq 10^6)，表示第 i 位朋友准备的礼物数量，接下来输入 a_i 个正整数 b_{i,j}(1 \leq b_{i,j} \leq 3000)，表示每份礼物的空间大小。

数据保证 a_i 的总乘积不超过 10^6，即 \prod_{i=1}^Na_i \leq 10^6。  

输出描述:

输出一行一个正整数，表示收取礼物的方案数，使背包恰好装满。
示例1

输入

复制 
2 10
2 3 4
3 7 6 7

输出

复制 
3

说明

当选择第 1 位朋友的第 1 份礼物和第 2 位朋友的第 1 份礼物时，礼物的总空间为 b_{1,1}+b_{2,1}=3+7=10，恰好装满背包。

当选择第 1 位朋友的第 1 份礼物和第 2 位朋友的第 3 份礼物时，礼物的总空间为 b_{1,1}+b_{2,3}=3+7=10，恰好装满背包。

当选择第 1 位朋友的第 2 份礼物和第 2 位朋友的第 2 份礼物时，礼物的总空间为 b_{1,2}+b_{2,2}=4+6=10，恰好装满背包。

除此之外不存在其他的方式恰好装满背包，所以方案数是 3。