Restaurant Recommendations

Time limit3sMemory limit128 MB

Summary

Restaurants recommend each other through a favorite digraph; find the cheapest cost to visit exactly k restaurants for every k, where each step's price depends on whether the recommender is a favorite of the current restaurant.

Level: Hard8 of 10
Topics: Graph, Dynamic programming, Shortest path, Greedy
Solved: No attempts yet

Problem

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.

Restaurant owner	Favorite restaurants	Recommended restaurants
1	2	1, 2, 3, 4
2	3	2, 3, 4
3	2, 4	2, 3, 4
4	none	4

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.

Input

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$ .

Output

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.

Hint

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).

Examples2

Example 1

Input

4
100 200 1 2
200 300 1 3
200 250 2 2 4
200 300 0

Expected output

Example 2

Input

9
100 100 0
300 400 1 4
350 500 1 2
550 600 3 7 3 2
900 300 2 7 6
250 400 1 5
900 900 2 9 8
400 500 1 9
500 400 0

Expected output