
ZOJ Problem Set  3358
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 kth 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 dth night? InputThere 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 ith (0 ≤ i < n) member, and watashi is always the 0th member. The (2*i+2)th line contains 3 integers, a_{i}, b_{i} and c_{i} (0 ≤ a_{i}, b_{i}, c_{i} ≤ 10000). The (2*i+3)th line begins with an integer m_{i} (0 ≤ m_{i} < n), followed by m_{i} pairs of integers. The jth (0 ≤ j < m_{i}) pair of integers, num_{j} (0 ≤ num_{j} < n and num_{j} ≠ i) and bgm_{j} (0 < bgm_{j} ≤ 10000), indicates that the ith member can help GDG to move to the num_{j}th member's dorm as long as she cost bgm_{j} RMB to bg him. It's guaranteed that each num_{j} is different from others. OutputFor each case, output the maximum amount of money GDG can possess before the dth night in a single line. Sample Input3 6 1 1 1 1 1 1 2 2 2 1 2 2 3 3 3 0 Sample Output9 Author: YU, Xiaoyao Source: ZOJ Monthly, July 2010 