식당 추천

루카의 도시에는 1번부터 $N$번까지 번호가 붙은 식당 $N$곳이 있고, 누구나 마음에 드는 식당을 찾을 수 있다. 식당 주인도 저마다 즐겨 찾는 식당이 있다. 식당 주인에게 추천을 부탁하면 주인은 자기 식당과 자신이 즐겨 찾는 식당을 추천하고, 그 식당 주인들이 추천할 식당도 모두 추천한다.

즉 식당 $i$의 주인이 추천하는 식당은 $i$ 자신과, 즐겨 찾는 식당을 따라 한 번 이상 이동해서 도달할 수 있는 모든 식당이다.

아래 표는 식당이 네 곳인 예시이다.

루카는 다음 방법으로 식당 몇 곳을 방문하려 한다.

• 첫 식당은 마음대로 고른다.
• 그다음 식당은 지금 있는 식당의 주인에게 추천을 받고, 추천받은 식당 중 아직 방문하지 않은 곳을 하나 골라서 정한다.
• 루카는 언제든지 방문을 끝낼 수 있다.

식당 $A$의 대표 메뉴 가격은 $X_A$와 $Y_A$ 두 가지이다. 루카가 식당에 들어가면 주인은 누가 이 식당을 추천했는지 묻는다. 추천한 사람이 식당 $B$의 주인이라면 루카가 내는 금액은 다음과 같다.

• 식당 $A$의 주인이 식당 $B$를 추천한다면 $X_A$쿠나
• 그렇지 않으면 $Y_A$쿠나. 루카는 첫 식당에서도 이 금액을 낸다.

이 방법으로 방문할 수 있는 식당 수의 최댓값을 $K$라고 하자. $1$ 이상 $K$ 이하의 모든 $k$에 대해, 루카가 식당을 정확히 $k$곳 방문하려면 최소 몇 쿠나가 필요한지 구하시오.

첫째 줄에 식당의 수 $N$이 주어진다. ($1 \le N \le 1000$)

다음 $N$개 줄에는 각각 정수 여러 개가 주어진다.

$i$번째 줄의 처음 두 수는 식당 $i$의 대표 메뉴 가격 $X_i$, $Y_i$이다. ($1 \le X_i, Y_i \le 10000$) 세 번째 수 $O_i$는 식당 $i$의 주인이 즐겨 찾는 식당의 수이다. ($0 \le O_i < N$) 나머지 $O_i$개 수는 즐겨 찾는 식당의 번호이며, 이 번호는 서로 다르고 $i$와 같은 번호는 없다.

루카가 방문할 수 있는 식당 수의 최댓값이 $K$일 때 $K$개 줄을 출력한다. $k$번째 줄에는 루카가 식당을 정확히 $k$곳 방문할 때 내야 하는 금액의 최솟값을 쿠나 단위로 출력한다.

첫 번째 예제에서 식당 한 곳을 가장 싸게 방문하는 방법은 식당 1(200쿠나)을 방문하는 것이다.

식당 두 곳을 가장 싸게 방문하려면 식당 3(250쿠나)을 방문한 뒤 식당 2(200쿠나)를 방문한다.

식당 세 곳을 가장 싸게 방문하려면 식당 1(200쿠나), 식당 3(250쿠나), 식당 2(200쿠나) 순서로 방문한다.

식당 네 곳을 가장 싸게 방문하려면 식당 1(200쿠나), 식당 3(250쿠나), 식당 2(200쿠나), 식당 4(300쿠나) 순서로 방문한다.