I I U C   O N L I N E   C O N T E S T   2 0 0 8

Problem F: The Sultan’s Feast

Input: standard input

Output: standard output

 

Our beloved sultan is back again, and he is really excited. He will be celebrating his 2nd year anniversary next month. He is arranging a feast for that. But that is where, he is facing some problems.

 

He is holding a grand feast, and every guest can bring any number of guests. And there guests can also bring their guests and so on. The problem is, he doesn’t like everyone, and dislike many of the guests. So, he decided, he won’t be inviting every one.

 

He has assigned a ‘like’ value to everyone in his guest list. If like value is positive, then he likes them, negative if he dislikes, and zero if neither.

 

Now, sultan wants to invite his friends in such a way that would maximize the sum of ‘like’ value of all guests.

 

Input

First line contains T, the number of test cases. Each test case starts with an integer N, the number of people in the guest list. The following N lines each starts with two integers, li and ri. li is the ‘like’ value of the i-th person, and ri is the number of people he likes to invite. Rest of the line contains ri integers, the other guests i-th guest likes to invite. All guests are numbered from 1 to N. There is a blank line before each test case.

 

Output

For each test case, output the case number followed by the maximum ‘like’ value, or print “Alas, sultan can't invite anyone!” if it’s not possible to invite anyone. Sultan can invite, as long as the sum is non negative.

 

Constraints

-           T ≤ 100

-           N ≤ 100

-           -10000 ≤ li ≤ 10000, for all i = 1, 2, …, N

-           1 ≤ ri ≤ N – 1

-           In the friend list, no person is listed twice, and all numbers in the list are between 1         and N.

 

Sample Input

Output for Sample Input

3

 

5

8 2 2 4

-9 1 5

7 1 4

0 1 5

-10 0

 

4

10 2 2 4

-2 1 4

12 1 4

-10 0

 

5

10 1 2

-12 1 3

2 1 5

12 1 5

-10 0

Case #1: Alas, sultan can't invite anyone!

Case #2: 10

Case #3: 4

 

Problem setter: Manzurur Rahman Khan