Restaurant Recommendations

Luka's town has $N$ restaurants, numbered from 1 to $N$, and everyone can find something to like there. The restaurant owners also have favorite restaurants that they like to visit. If you ask a restaurant owner for a recommendation, the owner recommends their own restaurant and their favorite restaurants, and also every restaurant that the owners of those favorites would recommend.

In other words, the owner of restaurant $i$ recommends restaurant $i$ itself and every restaurant that can be reached from $i$ by following favorites one or more times.

The table below shows an example with four restaurants.

Luka plans to visit several restaurants as follows:

• He chooses the first restaurant freely.
• To choose each next restaurant, he asks the owner of the current restaurant for a recommendation and picks one of the recommended restaurants that he has not visited yet.
• Luka can end the tour at any moment.

Each restaurant $A$ has two prices for its main menu, $X_A$ and $Y_A$. When Luka enters a restaurant, its owner asks him who recommended the restaurant. If that person is the owner of restaurant $B$, Luka pays:

• $X_A$ kuna if the owner of restaurant $A$ recommends restaurant $B$,
• $Y_A$ kuna otherwise. Luka also pays this amount at the first restaurant.

Let $K$ be the largest number of restaurants Luka can visit this way. For every $k$ from $1$ to $K$, find the minimum number of kuna Luka needs to visit exactly $k$ restaurants.

The first line contains an integer $N$ ($1 \le N \le 1000$), the number of restaurants.

Each of the next $N$ lines contains several integers.

The first two numbers on the $i$-th line are the main menu prices $X_i$ and $Y_i$ ($1 \le X_i, Y_i \le 10000$). The third number $O_i$ ($0 \le O_i < N$) is the number of favorite restaurants of the owner of restaurant $i$. The remaining $O_i$ numbers are the labels of those favorite restaurants. The labels are pairwise distinct, and none of them equals $i$.

If $K$ is the largest number of restaurants Luka can visit, print $K$ lines. On the $k$-th line, print the minimum number of kuna Luka must pay to visit exactly $k$ restaurants.

In the first example, the cheapest way to visit one restaurant is to visit restaurant 1 (200 kuna).

The cheapest way to visit two restaurants is to visit restaurant 3 (250 kuna) and then restaurant 2 (200 kuna).

The cheapest way to visit three restaurants is to visit restaurant 1 (200 kuna), restaurant 3 (250 kuna), and finally restaurant 2 (200 kuna).

The cheapest way to visit four restaurants is to visit restaurant 1 (200 kuna), restaurant 3 (250 kuna), restaurant 2 (200 kuna), and finally restaurant 4 (300 kuna).