402496: GYM100792 J Jealousy

Barry has just returned from a team building event and found his girlfriend Alice logged in his social network account, surfing through uploaded photos. An unpleasant conversation is now inevitable.

"Who are all these girls?" asks Alice.

"They... they are my friends' girlfriends," replies Barry.

Alice looks at the first photo.

"So, who are these?" demands Alice.

"Well... Cindy is Charlie's girlfriend and Darya... is Daniel's one?"

...Next photo...

"Three new girls! And whose friends are they, mm?"

"Eva is Eduard's, Frida is Freddy's and Julia...," — Barry now feels as he has stepped on a slippery ice — "...is a new Charlie’s girl!"

"Really, Charlie dumped Cindy?! For this frog? Strange."

...Next photo...

"And here? Darya, Frida, and?.."

"Katy. New Charlie's girl again."

"This time he did the right thing. Katy is a sweetheart."

And so it goes. There are n photos Alice will take a look at. On the i-th photo, there are a_i girls present. When Alice opens a new photo, for each girl pictured on it Barry should tell who is her current boyfriend. Fortunately, all k friends are present on each photo, making the task a bit easier than it could be. The only restriction is to name different friends for different girls while explaining a single photo.

While Barry tells his story, Alice calculates its suspiciousness. For each of k boys she keeps in mind who was his girl last time he was mentioned in the story. Every time Barry says that j-th boy is now in a relationship with the girl i, Alice increases the value of suspiciousness by q_i if and only if she keeps in mind that boy j has another girlfriend. Initially, she assumes all friends of Barry have no girlfriends. Of course, Barry wants to minimize the suspiciousness of his story.

Note that for two boys Alice may keep in mind that they are in a relationship with the same girl. However, that doesn't affect suspiciousness in any way.

The first line of the input contains three integers n, k and m (1 ≤ n ≤ 100, 0 ≤ k, m ≤ 100) — the number of photos Alice is going to look at, the number of friends on each photo and the number of different girls that can possibly be present on these photos respectively. The second line contains m integers q_i (0 ≤ q_i ≤ 1000) that define the values added to Alice's suspicion if the i-th girl becomes someone's girlfriend instead of another girl. Then follow n lines with descriptions of photos. Each description consists of an integer a_i — the number of girls on the i-th photo, followed by a_i distinct girls' indices g_i, j (0 ≤ a_i ≤ min(m, k), 1 ≤ g_i, j ≤ m).

The output must consist of n + 1 lines. The first line must contain a single integer — the minimal possible total suspiciousness of the story. After that, n lines describing the story itself must follow: for every photo, print a_i indiсes — the current boyfriend of each girl on the photo. Keep the order of the input data. Barry's friends are numbered from 1 to k.

3 4 6
3 5 4 6 10 1
2 1 2
3 3 4 5
3 2 4 6

5
1 2
1 3 4
2 3 4

6 2 3
1 10 100
1 1
2 2 3
2 1 2
2 1 3
1 3
1 1

111
1
1 2
2 1
2 1
1
2

The table below illustrates the answer for the second sample:

For each day the information Alice keeps in her mind is given. The value of suspiciousness increases by 10 on the second day, by 1 on the third day, and by 100 on the fourth day. The overall sum is 10 + 1 + 100 = 111.