‹ 上一题下一题 ›

s02201. 密码组合未做

1000 ms 256 MB 测试点 10 S-14·搜索进阶 S·算法自拟题 S-14 深度优先搜索广度优先搜索记忆化搜索搜索的剪枝优化双向广度优先搜索迭代加深搜索

文件读写输入s02201.in输出s02201.out

题目描述

一个 $L$ 位密码，第 $i$ 位上可以取的值由一个候选集合给出。一个密码的校验和定义为各位数字之和。求校验和恰好等于 $S$ 的密码个数。

输入格式

第一行两个整数 $L, S$ 。接下来 $L$ 行，第 $i$ 行先一个整数 $c_{i}$ （该位候选个数），随后 $c_{i}$ 个整数（候选数字）。

输出格式

一行一个整数，密码个数。

样例

输入

2 5
2 1 2
2 3 4

输出

数据范围

对于 30% 的数据： $L \leq 10$
对于 60% 的数据： $L \leq 20$
对于 100% 的数据： $L \leq 30$ ， $1 \leq c_{i} \leq 9$ ，候选数字 $0 \leq d \leq 9$ ， $0 \leq S \leq 270$ ， $1 \leq i \leq L$

输入

输出

答案