기계 가게

Elise Isabella Oya는 Cute Machine Shop에서 일한다. 이 가게는 여러 종류의 기계를 판매하며, 모든 기계는 공급업체에서 살 수 있다. 일부 기계는 가게에서 다른 기계들로 만들 수도 있고, 그 기계들 역시 또 다른 기계로 만들어질 수 있다.

예를 들어 기계 A는 기계 B와 C로 만들 수 있고, 기계 B는 기계 D와 E로 만들 수 있다. 이 경우 기계 A는 C, D, E로도 만들 수 있다.

Elise는 어떤 기계의 가격 견적을 요청받았다. 이에 답하려면 그 기계를 사서 얻든 직접 만들어 얻든, 가장 낮은 비용을 알아야 한다. 다른 기계로 기계를 만드는 데 드는 인건비는 무시해도 된다.

첫 줄에는 공백으로 구분된 정수 $N$과 $K$가 주어진다($1 \le K \le N \le 1000$). $N$은 서로 다른 기계의 개수이고, $K$는 Elise가 얻어야 하는 기계의 번호이다. 기계는 $1, \ldots, N$으로 번호가 매겨져 있다.

다음 $N$개의 줄은 번호 순서대로 기계를 설명한다. 각 줄의 첫 값은 기계 $i$를 사는 비용 $P_i$($0 \le P_i \le 10000$)이다. 기계를 사는 방법으로만 얻을 수 있으면 가격 뒤에 0이 오고, 그 줄에는 더 이상 데이터가 없다. 그렇지 않으면 가격 뒤에 기계 $i$를 만드는 데 필요한 다른 기계의 개수 $M_i$($1 \le M_i \le N$)가 오고, 이어서 그 기계들의 번호 $M_i$개가 공백으로 구분되어 주어진다. 이 $M_i$개의 번호는 항상 서로 다르다.

어떤 기계도 직접적으로든 간접적으로든 자기 자신의 구성 요소가 되지 않는다. 그래프 용어로 말하면 방향 비순환 그래프이다.

기계 $K$를 얻는 데 드는 최소 비용을 나타내는 정수 하나를 출력한다.