Green Dam Girl (GDG) became bankrupt recently, and watashi picked her up to his dorm. Some ZJU ICPC team members would like to support her.
There are n team members who would like to support her. A member will give GDG q RMB (Renminbi, the currency of China) at the k-th night when GDG lives in his dorm continuously without any moving, where:
q = ai , if k = 1;
q = bi , if k = 2;
q = ci , if k ≥ 3.
GDG will get the money in the next morning.
Every afternoon, GDG can choose to move or not. But she has too much baggage to move all by herself. Luckily, she can turn to the member whose dorm she is currently in for help. Of course, it's not free -- GDG needs to bg (means treat) the member. The member will tell GDG whose dorm he can help her to move to and how much money she will cost correspondingly. Here are some notes:
If GDG don't get enough money to bg, she can't move to the dorm directly;
GDG can only ask the member whose dorm she is currently in for help;
GDG can move more than once. So, in order to move to some dorm, GDG may need to bg many times.
At the 1st night, GDG lives in watashi's dorm without any money. How much money can GDG possess before the d-th night?
Input
There are multiple cases. For each case, the first line contains two integers, n (1 ≤ n ≤ 100) and d (1 ≤ d ≤ 100). There are 2*n lines next. The (2*i+2)-th and (2*i+3)-th lines describe the information of the i-th (0 ≤ i < n) member, and watashi is always the 0-th member.
The (2*i+2)-th line contains 3 integers, ai, bi and ci (0 ≤ ai, bi, ci ≤ 10000). The (2*i+3)-th line begins with an integer mi (0 ≤ mi < n), followed by mi pairs of integers. The j-th (0 ≤ j < mi) pair of integers, numj (0 ≤ numj < n and numj ≠ i) and bgmj (0 < bgmj ≤ 10000), indicates that the i-th member can help GDG to move to the numj-th member's dorm as long as she cost bgmj RMB to bg him. It's guaranteed that each numj is different from others.
Output
For each case, output the maximum amount of money GDG can possess before the d-th night in a single line.
Sample Input
3 6
1 1 1
1 1 1
2 2 2
1 2 2
3 3 3
0
Sample Output
9
