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.
Input
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. "A_{i} B_{i} C_{i} x_{1} x_{2} ... x_{Ai}". The ith kid has A_{i} distinct information. The information id is x_{1}, x_{2} ... x_{Ai}. He is going to share at least B_{i} information and at most C_{i} information. (0 ≤ B_{i} ≤ C_{i} ≤ A_{i}) 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.
Output
Just output the number of information that student can get at most.
Sample Input
2
2 1 2 3 4
0 0 0
2
2
2 1 1 5 6
1 1 1 5
2
Sample Output
2
2
Hint
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