Fax Compression

To store a fax image, a scanner first converts the image into a sequence. Each element of the sequence is an integer from 1 to 256.

The image does not have to be represented exactly. Each element may be replaced by one of four levels, 1, 86, 172, and 256. The levels are encoded by the following 2-bit codes.

Images often contain long regions of the same color. To encode such regions more compactly, the transformed sequence y1, y2, ..., yN is written as follows.

1. Write the 2-bit code of the first value y1.
2. For every later value, compare it with the previous transformed value.
   • If it is the same as the previous value, write 0.
   • If it is different, write 1 followed by the 2-bit code of the current value.

Suppose the original sequence is 2, 2, 2, 2, 2, 46, 2, 2. If it is transformed into 1, 1, 1, 1, 1, 86, 1, 1, the code is 0000001011000 and the total error is 1+1+1+1+1+40+1+1=47. If all values are transformed into 1, the total error increases to 1+1+1+1+1+45+1+1=52, but the code becomes the shorter string 000000000.

The cost of a transformation is defined as

total error + W × length of the transformation code.

Here W is the weight given in the input. If the original sequence is x1, x2, ..., xN and the transformed sequence is y1, y2, ..., yN, the total error is Σ|xi - yi|.

For the sequence above with W = 100, transforming it into 1, 1, 1, 1, 1, 86, 1, 1 has cost 47 + 100 × 13 = 1347. Transforming every value into 1 has cost 52 + 100 × 9 = 952.

Find a transformation with minimum cost.

The first line contains the sequence length N and the weight W.

1 ≤ N ≤ 50, 0 ≤ W ≤ 100

Each of the next N lines contains one element of the sequence, in order. Every element is an integer from 1 to 256.

Print the minimum transformation cost on the first line.

On the second line, print a transformation code that achieves that cost.