I :: Zombies

Time Limit: 12 Seconds    Memory Limit: 65536 KB

The “Institute of Changing Prot Chromosomes” (ICPC) has hired new zombie-terminator crew due to some dangerous experiments. There exists a room in this institute for keeping the zombies, and all the people in this room are either zombies or guards. If the zombies escape, the guards’ duty is to make sure they are stopped before reaching the entrance to the processor center. The institute has a large number of rooms, some of which are connected to each other, and in each room - with the exception of the zombies’ room - there exist an unlimited number of researchers. Due to security reasons, there is only one entrance to the processor center, the most important place in the institute.

Whenever the zombies enter a room, first every guard attacks a zombie, and as the result of this attack, both the zombie and the guard would be killed. Afterwards, if any living zombies still exist in the room, they each attack a researcher, transforming the researcher into a zombie as a result. Meanwhile, all other researchers in the room commit suicide in order not to become zombies. Hence, eventually the number of the zombies in the room would be doubled and all other people in the room would die. After all the living people in the room are transformed into zombies, the zombies go to the adjacent rooms in which there still exist living people. Assuming there are k rooms with living people adjacent to the current room, the zombies would be divided into k groups of equal size and move to these k rooms. If the number of the zombies is not divisible by k, the remainder of the zombies stay in the current room.

All the zombies move simultaneously and it is possible for two different groups of zombies to enter a new room at the same time. Also when the zombies reach the room which has the entrance to the processor center, they all exit to the processor center and not any other room - if they survive the attacks in the current room. Each room has a capacity of at most 109 zombies and all zombies trying to enter a filled-up room would be killed. An example of the procedure of the zombies’ invasion is shown below. (Z: Zombie, G: Guard, X: Empty, Ex: Exit)

You are given the map of the institute (including the location of the processor center entrance and the labs) and the number of the guards in each room. You must find the most number of zombies that could be controlled by the guards in the institute (If there are more zombies than this number, they can exit to the processor center, and less zombies would be killed before reaching the exit.)

Input

The input contains several test cases.

In the first line of input comes T (0 < T ≤ 32), the number of test cases.

In each test, the first line contains 1 < N < 1000, 0 < L < N, and 0 < X < N representing the number of labs, the number of the zombies room, and the number of the lab that has the entrance to the processor center respectively. In the next N lines the information about each lab is entered as followed:

At the beginning of line i + 2, you are given the number of guards in room i (0 ≤ Guards ≤ 10⁹). Next, you are given a number m as the number of the rooms adjacent to room i, followed by m numbers specifying these rooms.

Output

For each test case, print a line containing an integer representing the maximum number of zombies that could be stopped by the guards.

Sample Input

2
4 0 3
0 2 1 2
0 3 0 2 3
3 3 0 1 3
0 2 1 2
4 0 3
1 2 1 2
5 2 0 3
4 2 0 3
1 2 1 2

Sample Output

1
10

Submit

Source: 13th Iran Nationwide Internet Contest - UT