칩 만들기 2

당신은 칩을 만들기 위해 기판에 N개의 부품을 장착했다. 각각의 부품을 작동시키기 위해서는 전원을 연결해야 하는데, 기판에 연결할 수 있는 전원 선이 K개 밖에 없었다. 당신은 이 K개의 전원 선을 기판의 아래쪽에 연결하고, 기판의 위쪽에서 부품을 연결하여 전원을 나눠 쓰기로 하였다. 이때 다음과 같은 조건을 지켜야 한다.

1. 한 개의 전원 선은 최대 두 개의 부품에만 사용될 수 있다.
2. 기판의 위쪽에 연결한 전선들은 서로 꼬여서는 안 된다. 하지만 하나의 전선이 덮는 구역 안에 다른 전선이 연결될 수는 있다.
3. 각각의 부품에는 그 부품의 중요도가 있다. 우리가 만든 칩의 중요도는, 한 개의 전원 선이 한 개의 부품에 연결될 때는 그 부품의 중요도를 더하고, 두 개의 부품에 연결될 때는 각 부품의 중요도를 곱한 것을 더한 값으로 표현된다. 이와 같은 중요도를 최대로 하는 칩을 만드는 것이 목적이다.

제일 왼쪽의 예는 기판의 위쪽에 연결한 전선이 꼬이는 경우로 올바르지 않은 경우이다. 두 번째 경우는 올바른 연결이고, 중요도가 4 × 4 + 3 × 5 = 31이다. 세 번째 경우는 올바른 경우이지만, 중요도가 4 × 4 + 5 = 21로 최대가 아니다. 이 칩에서 만들 수 있는 최대 중요도는 3 × 4 + 4 × 5 = 32이다.

첫째 줄에 두 정수 N(1 ≤ N ≤ 50), K(1 ≤ K ≤ 20)이 주어진다. 다음 줄에는 N개의 정수로 각 부품의 중요도가 차례로 주어진다. 부품의 중요도는 1,000 이하의 음이 아닌 정수이다.

처음 K개의 줄에는 전원을 연결한 부품의 번호를 출력한다. 사용하지 않은 전원에 대해서는 0을 출력한다. 다음 N개의 줄에는 각 부품이 몇 번 부품과 전원을 공유하는지를 출력한다. 전원을 혼자 사용하는 경우에는 자기 자신을 출력하고, 전원을 사용하지 않는 경우에는 0을 출력한다.