J. Jewel Collection
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A billionaire with a vast and diverse collection of jewels, each featuring up to two distinct colors, has decided to showcase his collection in a grand exhibition. His aim is to arrange the jewels so that every color present in his collection is prominently displayed.

He wants to ensure that every color is uniquely represented by one jewel. If a jewel has the color $$$c_1$$$ and $$$c_2$$$, and is used to represent the color $$$c_1$$$, it cannot be used again to represent the color $$$c_2$$$, and vice versa.

In addition to showcasing every color, the billionaire wants to flaunt his wealth by maximizing the total price of the displayed jewels as well.

Your task is to assist him in selecting the jewels for the exhibition according to these criteria.

Input

The first line contains two integers $$$N$$$ and $$$C$$$ $$$(1 \le N,C \le 200,000)$$$ — the number of jewels, and the number of colors, respectively.

The $$$i^{th}$$$ line of the following $$$N$$$ lines describes the $$$i$$$-th jewel in the format of $$$t$$$ $$$c_1$$$ $$$c_2$$$ ... $$$c_t$$$ $$$v$$$ $$$(1\le t \le 2, 1 \le c_1 , c_2 , \dots , c_t \le C, 1 \le v \le 1,000,000)$$$ — the $$$i$$$-th jewel has $$$t$$$ colors: $$$c_1$$$, $$$c_2$$$, ... $$$c_t$$$ with the price value of $$$v$$$.

Output

The first line contains an integer $$$W$$$, the maximum total price.

The second line contains $$$C$$$ non-repeated integers, the jewel to display in the exhibition for each color from color $$$1$$$ to color $$$C$$$, respectively. If there are multiple possible rearrangements, output any of them.

If it is impossible to set up the display, output $$$-1$$$.

Examples
Input
7 4
2 1 3 2
2 2 4 4
2 2 4 5
2 2 3 1
2 1 3 5
1 2 6
1 4 3
Output
18
1 6 5 3
Input
4 3
2 1 3 1
2 1 3 2
1 1 2
1 3 1
Output
-1
Note

In the second example, it is impossible because there is no jewel with color $$$2$$$.