405130: GYM101804 C China Adventures

The ACM ICPC World Finals is a huge event! On 2018 the World Finals was at Beijing, China.

The chinese culture is way different than brazilian culture. They eat

(as they translated: "Bad fish chips")

and

(as they translated: "Sauteed chicken on the left")

Their traffic is crazy, with cars driving on the cycle path, motorcycles driving the wrong way or on the sidewalk. But, the weirdest of all, they use QR-codes for everything.

A QR-code is a square image, in this case a $$$21 \times 21$$$ pixel matrix, that each pixel is either black or white. The code carries some information, usually an URL or a text, and can be read by almost all modern smartphones.

They use QR-codes so that people don't have to copy text all the time. They just have to open their smartphone's camera and the magic happens.

During a tour on Beijing, Lucas Santana, the Handsome, noticed that to visit some tourist places he needed to know the QR-code to buy the tickets for that place. Since he's a very smart guy, he decided to create a mobile application to draw the QR-codes, instead of searching for them.

The mobile application works as follow: it starts with a $$$21 \times 21$$$ white pixel matrix. You can click any pixel to swap it's color from white to black or from black to white in 1 decisecond. Also, you can restart the application at any time to have an all white pixel matrix again, but it take $$$a$$$ deciseconds to do so. When you complete the QR-code, you can assume you can enter the tourist place.

Lucas knows the QR-code of $$$n$$$ places he wants to visit. He doesn't care about the order he visits the places, but, since he only have a few days left on China, he wants to spend the least time as possible drawing the QR-codes. Can you help him saying the minimum amount of deciseconds to draw all $$$n$$$ QR-codes, the order he should visit the places and when he should restart the application?

He will not visit the same place more than once. (Don't even try this. He will give you a wrong answer!).

The first line of input contains two integers, $$$n$$$ and $$$a$$$ ($$$1 \leq n \leq 18$$$, $$$1 \leq a \leq 50$$$) — the number of places he wants to visit and the total time to restart the application.

The next lines contains the QR-codes of the places separated by empty lines. There will be $$$n$$$ QR-codes, each having $$$21$$$ lines of $$$21$$$ digits being $$$0$$$ or $$$1$$$. Digit $$$0$$$ means a white pixel and $$$1$$$ a black pixel.

Print the minimum amount of deciseconds to draw all QR-codes followed by at least $$$n$$$ lines and at most $$$2 \times n - 1$$$ lines. Each line should have one number between $$$1$$$ and $$$n$$$, meaning that he must visit the place $$$i$$$, or one character "*" (without quotes), meaning that he must restart the application.

All numbers should be distinct.

If there are multiple answers, print any of them.

1 10
111111100101101111111
100000101101001000001
101110101100101011101
101110100101001011101
101110101000101011101
100000101001101000001
111111101010101111111
000000001111100000000
110100110110001110110
111101000100000110110
111110111110101101101
001110001011001101001
000111110010110100100
000000001001000100000
111111101110011110110
100000100011110001000
101110100101011100010
101110101111000010011
101110100100100110101
100000101010011100000
111111101101100010010

228
1

In sample case, he should just draw the only QR-code available and visit the place. The QR-code is: