Find A Job

It is difficult to find a job!
Now poor yifenfei wants to find a job in N days. Every day he will take part in a company's interview to get more offers. You know, everyone wants to succeed in every interview but it’s not so easy, you must satisfy some requirements.
For example: Google: algorithm(100) && C++(100). That means the ability of algorithm must not less than 100, the same to C++. And some skills can replace each other. For example: If C++ and Java can replace each other, than algorithm and Java larger or equal than 100 also satisfy the requisition of Google. Meanwhile, yifenfei will make progress in some skills after each interview. For example: algorithm(10) && C++(10). That means after an interview, the ability of algorithm will increase 10 and the ability of C++ will increase 10.
Before the first interview, yifenfei can choose one skill and let the ability of this skill reach D degree, the others are 0.

The first line of the input contains an integer T (1<=T<=100) which means the number of test cases.
For each case:
First line two integers N, D. (1 <= N <= 100, 0 <= D <= 100)
Then several lines follow. Each line contains 2 – 5 skills separated by “ # ” which means these skills can replace each other. End by “#end#”!
Then N*2 lines follow, every two lines describe the interview information day by day.
The format is:
First: Company Name : Skill_1(the least degree D1) && Skill_2(the least degree D2) && .....Skill_k(the least degree Dk).
Second: Skill_1(the increasing degree I1) && Skill_2(the increasing degree I2) && .....Skill_m(the increasing degree Im).
(0 <= k, m <=4, 0 <= Di, Ii < 2^31)
The number of skills is not larger than 10000, the length of company name and skill name will not more than 100, Company name and skill name will not contain leading and trailing blank ,‘&’, ’(’, ’)’ and ’#’.

For each case output the maximum number of different companies will give offer to yifenfei.

1
2 10
C++ #  Java
#end#
Google  :    algorithm(100)    &&  C++(100)
          algorithm(90)  &&  C++(10)
Blizzard Entertainment  :   algorithm(80)   &&   C++(20)
                      algorithm(50)   &&   C++(10)

1

HDU 2009-11 Programming Contest