提示: 欢迎访问OurACM平台。
Problem 1513 Treasure

Accept: 92    Submit: 200
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

One day, Argentmoon is dreaming in the class. He reaches such a wonderful place that some guys tell him there is a lot of treasure in the maze he is facing.

Of course, poor Argentmoon won’t miss this great chance. But when he enters the maze, an eidolon who call itself guardianship of the maze appears, “Hi, boy. If you want to get the treasure, you must obey my rules, or you will be punished.”

Rules are as follows:

There’re lots of rooms in the maze with or without treasure, every treasure has a number (0 ~ 100) to denote the value. Initially, he is in the room 1, and every room is connected to some other rooms. You can only reach one room at most once. If he begins at a random room, he can reach any room in the maze by only one path.

Cute acmer, please help poor Argentmoon to get as much treasure as possible.

Input

The input consists of several test cases. For each case, first line is an integer N (1 <= N <= 10,000), indicating the number of room in the maze, and N lines follows, each line of which consists of the number K, T, M (0<=M<=100), which specifies room K has treasure of value T, and M doors direct to other rooms. Then M integers follow, each of which specifies the number of the room connected to the room K. All rooms are numbered from 1 ~ N.

Output

Output the maximum value of the treasure Argentmoon can get in the maze and the number of rooms he reached. If there is a tie for value, output the one with smaller number of reached rooms.

Sample Input

5 1 10 2 2 3 5 20 0 4 100 0 2 1 1 4 3 5 1 5

Sample Output

111 3

Source

FOJ月赛-2007年6月

Submit  Back  Status  Discuss