War

Country W is at war with N countries. Through intelligence, it learned that if at least M of those countries are conquered or forced to surrender, every remaining country will surrender as well.

The time needed to directly conquer each country may be different. Because all military power must be focused on the country currently being attacked, only one country can be fought at any moment. The goal is to reach the required number of countries as quickly as possible.

There may be vassal relationships between countries. If country A is a vassal of country B, then directly conquering country B also makes country A surrender automatically. These relationships are hierarchical, so conquering a country makes all of its descendant vassals surrender as well.

If a country is a vassal, it has exactly one direct superior. A country may have any number of direct vassals.

Given N, M, the direct conquest time of each country, and the vassal relationships, find the minimum number of days needed to conquer or force the surrender of at least M countries.

The first line contains the number of countries N (1 <= N <= 200) and the required number M (0 <= M <= N).

Each of the next N lines describes one country. A line contains the country name, the number of days needed to directly conquer that country, followed by zero or more names of its direct vassals. A country name is a string of uppercase and lowercase English letters with length from 1 to 100. The names after the conquest time are exactly the direct vassals of the country on that line.

Print the minimum number of days needed to conquer or force the surrender of at least M countries.

Directly conquering CountryB also makes its vassal CountryA surrender, so 2 countries are secured.