전쟁

현재 W국은 N개의 나라와 전쟁 중이다. W국은 첩자를 통해, N개의 나라 중 M개 이상의 나라를 정복하거나 항복시키면 나머지 나라들이 모두 항복한다는 정보를 얻었다.

각 나라를 직접 정복하는 데 걸리는 일수는 서로 다를 수 있다. 한 나라를 정복하는 동안에는 모든 전력을 그 나라에 집중해야 하므로, 동시에 둘 이상의 나라를 공격할 수 없다. 목표는 필요한 수의 나라를 최대한 빨리 정복하거나 항복시키는 것이다.

나라들 사이에는 속국 관계가 있을 수 있다. 나라 A가 나라 B의 속국이면, 나라 B를 직접 정복할 때 나라 A도 자동으로 항복한다. 속국 관계는 계층적으로 이어지므로, 어떤 나라를 정복하면 그 나라의 모든 하위 속국도 함께 항복한다.

어떤 나라가 속국이라면 속한 상위 나라는 하나뿐이다. 한 나라가 여러 나라를 직접 속국으로 둘 수는 있다.

N, M, 각 나라의 정복 일수, 속국 관계가 주어질 때 M개 이상의 나라를 정복하거나 항복시키는 데 필요한 최소 일수를 구하시오.

첫째 줄에 나라의 개수 N(1 <= N <= 200)과 필요한 나라의 수 M(0 <= M <= N)이 주어진다.

이어서 N개의 줄에 각 나라의 정보가 주어진다. 각 줄은 나라 이름, 그 나라를 직접 정복하는 데 걸리는 일수, 그리고 0개 이상의 직접 속국 이름으로 이루어진다. 나라 이름은 길이 1 이상 100 이하의 알파벳 대소문자 문자열이다. 한 줄에서 정복 일수 뒤에 적힌 나라들은 모두 현재 나라의 직접 속국이다.

M개 이상의 나라를 최대한 빨리 정복하거나 항복시키는 데 필요한 최소 일수를 출력한다.

CountryB를 직접 정복하면 CountryB의 속국인 CountryA도 자동으로 항복하므로, 총 2개 나라를 확보할 수 있다.