팩스 압축

팩스 이미지를 저장하려면 스캐너가 읽은 이미지를 수열로 바꾼 뒤 압축해야 한다. 스캐너가 만든 수열의 각 원소는 1 이상 256 이하의 정수이다.

이미지를 반드시 원래 값 그대로 표현할 필요는 없다. 각 원소를 네 가지 레벨 1, 86, 172, 256 중 하나로 바꾸어 표현할 수 있고, 각 레벨은 다음 2비트 코드에 대응된다.

이미지에는 같은 색이 이어지는 영역이 많다. 이런 영역을 더 짧게 표현하기 위해 변환한 수열 y1, y2, ..., yN을 다음 방식으로 코드화한다.

1. 첫 번째 값 y1은 위 표의 2비트 코드로 그대로 쓴다.
2. 두 번째 값부터는 바로 앞 값과 비교한다.
   • 앞 값과 같으면 0을 쓴다.
   • 앞 값과 다르면 1을 쓴 뒤, 현재 값에 해당하는 2비트 코드를 이어 쓴다.

원래 수열이 2, 2, 2, 2, 2, 46, 2, 2라고 하자. 이를 1, 1, 1, 1, 1, 86, 1, 1로 바꾸면 코드는 0000001011000이고 전체 오차는 1+1+1+1+1+40+1+1=47이다. 반면 모든 값을 1로 바꾸면 전체 오차는 1+1+1+1+1+45+1+1=52로 더 크지만, 코드는 000000000으로 더 짧아진다.

변환 비용은 다음 값으로 정의한다.

전체 오차 + W × 변환 코드의 길이

여기서 W는 입력으로 주어지는 가중치이다. 원래 수열을 x1, x2, ..., xN, 변환한 수열을 y1, y2, ..., yN이라고 할 때 전체 오차는 Σ|xi - yi|이다.

예를 들어 위 수열에서 W = 100이라면 1, 1, 1, 1, 1, 86, 1, 1로 바꾼 비용은 47 + 100 × 13 = 1347이다. 모든 값을 1로 바꾸면 비용은 52 + 100 × 9 = 952가 된다.

가능한 변환 중 비용이 최소가 되도록 하라.

첫째 줄에 수열의 길이 N과 가중치 W가 주어진다.

1 ≤ N ≤ 50, 0 ≤ W ≤ 100

다음 N개의 줄에는 수열의 원소가 순서대로 하나씩 주어진다. 각 원소는 1 이상 256 이하의 정수이다.

첫째 줄에 최소 변환 비용을 출력한다.

둘째 줄에 그 비용을 만드는 변환 코드를 출력한다.