세 회의실의 장비 꾸러미

문제

연수 행사를 준비하는 운영자는 장비를 빌려 주는 회의실 가운데 정확히 세 곳을 선택하려 한다. 행사에서 필요한 장비 종류는 1번부터 M번까지이다. 각 회의실에는 이 장비들 중 일부가 준비되어 있으며, 회의실을 선택하면 그곳의 장비를 행사장으로 모두 가져올 수 있다. 같은 종류의 장비가 여러 회의실에 있더라도 행사에는 한 종류가 확보된 것으로만 센다. 회의실은 입력 순서대로 1번부터 N번까지 번호가 붙는다. i번 회의실을 선택하는 데 드는 비용은 C_i이다. 장비를 일부만 가져오더라도 비용은 같으며, 선택한 세 회의실의 비용을 모두 더한 값이 총비용이다. 장비를 하나도 보유하지 않은 회의실도 있을 수 있다. 운영상의 계약 조건 때문에 필요한 장비를 두 곳에서 모두 확보할 수 있더라도 세 번째 회의실을 추가하여 정확히 세 곳을 선택해야 한다. 장비 보유 현황은 정수 B_i로 주어진다. B_i의 이진 표현에서 오른쪽부터 j번째 자리가 1이면 i번 회의실에 j번 장비가 있다는 뜻이다. 예를 들어 M이 4일 때 값 10은 이진수 1010이므로 2번과 4번 장비가 있다는 뜻이다. 값 0은 보유 장비가 없다는 뜻이다. 주어진 M종류 이외의 장비는 입력에 포함되지 않는다. 서로 다른 회의실 세 곳을 골라 모든 종류의 장비를 적어도 하나씩 확보해야 한다. 가능한 선택 중 총비용이 가장 작은 것을 구한다. 총비용이 같은 선택이 여러 개이면 각 선택의 회의실 번호를 오름차순으로 나열한 뒤, 앞에서부터 비교하여 처음 다른 번호가 더 작은 선택을 고른다. 같은 회의실을 여러 번 선택할 수 없으며, 모든 장비를 확보하는 선택이 없으면 불가능하다고 출력한다.

입력

첫째 줄에 정수 N과 M이 주어진다. 3 ≤ N ≤ 120, 1 ≤ M ≤ 20이다.
다음 N개 줄의 i번째 줄에 정수 C_i와 B_i가 주어진다. 1 ≤ C_i ≤ 999, 0 ≤ B_i ≤ 2^M-1이다.

출력

가능한 선택이 있으면 첫째 줄에 최소 총비용을 출력하고, 둘째 줄에 선택한 세 회의실의 번호를 오름차순으로 공백으로 구분하여 출력한다. 최소 총비용이 같은 경우에는 지문의 번호 비교 규칙을 따른다. 가능한 선택이 없으면 첫째 줄에 -1만 출력한다.

4 3
4 1
2 2
3 4
1 3

6
2 3 4

3 2
1 1
2 1
3 1

-1

4 1
2 1
2 0
2 1
2 0

6
1 2 3

출처: Devin.KR 자체 제작