Completing favorite game

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef has a nice job. Actually he doesn't even remember what he is supposed to do there, because he just plays videogames all the time, exactly h hours every working day!
Recently he got bored of just randomly playing videogames and decided to complete all the levels of his favorite Game as fast as possible.
The Game consists of n levels numbered with integers from 1 to n. After completing every level, some small number of new levels is unlocked. The structure of the Game levels is a tree with the root in level 1, i.e. every level (except for 1) has a unique level that unlocks it and level 1 is the only level that is considered unlocked at the very beginning. Chef has completed his favorite Game lots of times, so he knows that he needs exactly t_{i} hours to complete level i. Due to specifics of the Game every level should be completed entirely within one working day, i.e. Chef cannot start a level on Thursday, and finish it Friday morning.
Overall the gameplay proceeds as follows:
 There is a stack S that initially contains only the level 1
 Chef pops the topmost level out of the stack. Let's call this level x
 Chef spends t_{x} hours to complete level x. Note that he doesn't want to stay at work longer than for h hours, so if there is not enough time left today Chef will complete level x the next working day morning.
 After completing level x some m_{x} new levels get unlocked
 Chef places all the m_{x} unlocked levels on the top of the stack S in an arbitrary order, i.e. he is free to choose any order he likes
 If stack S is empty, the Game is considered completed, otherwise Chef goes back to the step 2
Can you help Chef figure out the minimum number of working days necessary to complete the Game?
Input
The first line of the input contains an integer T denoting the number of test cases.
For each test case, the first line of input contains two integers n and h.
The next line contains n spaceseparated integers ― t_{1}, t_{2}, ..., t_{n}.
The following n lines describe the structure of Game's levels: the xth of them contains an integer m_{x} followed by m_{x} integers ― the levels that get unlocked after completing level x.
Output
For each test case, output a single integer ― the minimum number of working days necessary to complete the Game.
Constraints
 1 ≤ T ≤ 10
 1 ≤ n ≤ 1000
 1 ≤ t_{i} ≤ h ≤ 24
 0 ≤ m_{x} ≤ 10
 It is guaranteed that the structure of the Game levels is a tree, i.e. it is possible to unlock all n levels and every level (except for 1) has exactly one other level that unlocks it.
Subtasks
 Subtask #1: n ≤ 9 (7 points)
 Subtask #2: m_{x} ≤ 2 (20 points)
 Subtask #3: n ≤ 100; h ≤ 8 (27 points)
 Subtask #4: Original constraints (46 points)
Example
Input: 2 5 24 13 24 22 12 16 1 3 0 2 2 5 0 1 4 10 8 1 4 3 1 7 3 2 2 4 4 3 2 5 10 2 3 4 0 0 1 6 3 7 8 9 0 0 0 0 Output: 5 4
Explanation
Example case 1: Chef has to complete every level during separate working days, and so to complete all 5 levels he needs 5 working days.
Example case 2: Chef will complete the Game if he will always push unlocked levels into stack starting with the largest indexed one and ending with the smallest indexed one. That is, after Chef completes level 1 he first pushes level 10 (S = [10]), then level 5 (S = [10, 5]) and then level 2 (S = [10, 5, 2]). So the second level Chef will play is 2.
Author:  alex_2oo8 
Tester:  xcwgf666 
Editorial  https://discuss.codechef.com/problems/FAVGAME 
Tags  alex_2oo8, dfs, dynamicprogramming, march17, medium, tree 
Date Added:  26082016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions