The Core of Power#533
The ancient realm of Mystara is under siege. Dark forces have emerged from the shadows, seeking to destroy the protective magic that has kept the land safe for centuries. The Wizard's Council knows their greatest challenge has arrived.
Across Mystara stand ancient wizard towers, connected by a network of magical ley lines that pulse with arcane energy. Each tower houses a repository of mana crystals — the source of all magical power. The Council has discovered that to maintain a tower's protective spells against the darkness, the wizards must channel at least mana crystals. A tower can draw upon the mana stored within its own walls, as well as from any tower directly connected to it by a ley line, with no intermediate towers. Mana from more distant towers cannot be channeled quickly enough. The Council also knows that the dark forces will assault only one tower at a time — so the mana in a tower can be used to power both that tower's defenses and those of any of its directly connected neighbors. However, if a tower's defenses fail, the Council must assume that the tower will be corrupted by darkness and its mana crystals will be consumed, unable to help defend Mystara. In the diagram below, suppose K = 10. Tower might appear well protected, but it will eventually fall to darkness.
The Archmage seeks to identify the Core of Power — the largest possible network of towers that can sustain each other's protective magic, even if all other towers are consumed by darkness.
More formally, a tower can maintain its defenses if it can channel at least mana crystals from itself and the towers directly connected to it by ley lines. A network of towers is defensible if every tower in it can maintain its defenses using only mana from itself and connected towers within the network. The Core of Power is the largest possible defensible network of towers — that is, no other defensible network contains more towers.
There will be several data sets. Each set begins with two integers, and , where is the number of towers (3 \le N \le 1000) and is the number of mana crystals required to maintain a tower's defenses.
The towers are numbered through N-1.
The next lines describe the towers, starting with tower . Each description line begins with an integer , indicating the number of mana crystals stored in that tower (0 \le T \le 10000). This is followed by an integer , indicating the number of ley lines emanating from that tower, and then integers, giving the towers those ley lines connect to. No two ley lines connect the same pair of towers, so every tower in each list is unique. No ley line loops from a tower back to itself. The ley lines are bidirectional, so if tower is listed for tower , then tower is guaranteed to be listed for tower in the input. The input ends with a line containing two space-separated s.
For each data set, print two integers on a single line: the number of towers in the Core of Power, and the total number of mana crystals in the Core of Power. Separate the integers with a space. There should be no blank lines between outputs.
Example 1