93 - ZOJ Monthly, July 2010 - G
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:
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:
At the 1st night, GDG lives in watashi's dorm without any money. How much money can GDG possess before the d-th night?
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.
For each case, output the maximum amount of money GDG can possess before the d-th night in a single line.
3 6 1 1 1 1 1 1 2 2 2 1 2 2 3 3 3 0
Author: YU, Xiaoyao
Source: ZOJ Monthly, July 2010