Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3642
Just Another Information Sharing Problem

Time Limit: 2 Seconds      Memory Limit: 65536 KB

There is going to be another test in the kindergarten. Again the teacher has already told every kid some information about the test in advance. This time, all the children share their information with others. But everyone just share some of his information. The teacher want to know how many information someone can get at most.


There are multiple cases, about 50 cases.
The first line of each case contains an integer n, indicating there are n kids.
The following n lines describe the state of the ith student. "Ai Bi Ci x1 x2 ... xAi". The ith kid has Ai distinct information. The information id is x1, x2 ... xAi. He is going to share at least Bi information and at most Ci information. (0 ≤ BiCiAi) When some kid share 0 information with others, he is still in the sharing state, and get the information shared by others(Though he doesn't provide anything).
The next line is a number m. You should find how many information kid m can get at most. (1 ≤ m ≤ n)The index of kids is from 1 to n.

n is less than 200, and is positive. The information id is among [1,1000000]. There would be 200 distinct information at most.
The number of information each student carry is among [0,10]. Different kids may carry same information.

Each information can be shared by different kids at the same time.


Just output the number of information that student can get at most.

Sample Input

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

Sample Output



Sample 1: kid 1 shares both information, kid 2 shares nothing. kid 2 can have 2 information.
Sample 2: kid 1 shares (6), kid 2 shares (5). Then kid 2 can have 2 information.

Author: LI, Chao
Contest: ZOJ Monthly, August 2012
Submit    Status