RAINBOW - Rainbow Ride

题意翻译

Mr.Raju和他的大家庭正在Chennai度假。他们参观了MGM(米高梅),看到了彩虹之旅。他们希望可以享受这次旅行。但是,这其中也存在一些问题。每个家庭成员都喜欢另一个家庭成员,每个人都坚持认为,只有当那个人喜欢的人和喜欢那个人的人都上车时,Ta才会上车。如果有人不喜欢任何人,没有人喜欢他,他可能会来兜风。 你被拉进去解决这个难题。给出家庭中每个人的体重,以及他们喜欢的人的列表,以及彩虹能够安全承受的最大重量,计算家庭中能够上彩虹的最大人数。

题目描述

Mr.Raju and his extended family are on vacation in Chennai. They visit MGM and see the Rainbow ride. They want to enjoy the ride. However, there are some problems. Each person in the family likes some other people in the family. Each person insists that he or she will go on the ride only if all the people whom that person likes and all the people who like that person also go on the ride. If someone doesn't like anyone and no one likes him, he may come for the ride. You have been roped in to solve this dilemma. Given the weight of the each person in the family, and the list of people they like, and the maximum weight that the Rainbow can bear safely, calculate the maximum number of people in the family who can go on the rainbow.

输入输出格式

输入格式


There will be multiple test cases in the input. For our convenience the family members are numbered from 1 to n. Each test case begins with a line containing two integers **n** ( 1 ≤ n ≤ 1000 ) and **C** ( 0 ≤ C ≤ 1000 ), where n is the number of people in the family and C the maximum capacity of the ride in kilograms. The next line contains n space separated integers with the **i**th integer giving the weight of the **i** th family member. These weights are positive and less than or equal to 200 kilograms. Then n lines follow. Each line contains a sequence of integers separated by spaces. The first integer **k $ _{i} $** gives the number of people in the family person **i** likes, followed by the persons **i** likes. An empty line separates each test case. The end of input is indicated by n=0 and C=0 and it should not be processed.There are atmost 50 test cases.

输出格式


For each test case output on a separate line the maximum number of persons that can take the ride under the given conditions.

输入输出样例

输入样例 #1

5 200
50 50 50 50 50
1 2
1 3
0
1 5
1 4

3 200
100 100 100
1 2
1 3
1 1

0 0

输出样例 #1

3
0