다리 놓기

한 대기업이 새 사무 단지를 계획하고 있다. 단지는 건물 A와 건물 B, 두 동으로 이루어지며, 근무 시간 동안 한 건물에서 다른 건물로 이동하는 사람이 많을 것으로 예상된다. 매번 지상층까지 내려갔다가 다시 올라가는 수고를 덜기 위해, 두 건물 사이에 다리를 몇 개 놓으려고 한다.

다리를 가장 좋은 위치에 놓는 프로그램을 작성하라. 모든 다리는 수평으로 놓이며, 건물 A의 x층과 건물 B의 같은 x층을 잇는다. 최적의 배치란 이동한 계단 수의 총합이 최소가 되는 배치를 말한다. 이때 총합은 건물 A의 모든 출발 층과 건물 B의 모든 도착 층에 대해 더한 값이다. (즉, 건물 A의 x층에서 건물 B의 y층으로 이동하는 횟수는 모든 x와 y에 대해 1로 같다고 가정한다.) 단, 다리를 놓은 뒤에도 지상층까지 내려가 반대편 건물로 건너가는 편이 계단을 덜 오르내린다면 그렇게 이동할 수도 있다.

여러 다리 배치가 똑같이 최적일 수 있다. 이런 경우에는 다리가 더 낮게 놓인 배치를 택한다. 예를 들어 1, 2, 3은 1, 2, 4보다, 1, 8, 9는 2, 3, 4보다 우선한다.

한 줄 이상이 주어지며, 각 줄에는 세 개의 양의 정수가 있다. 차례대로 두 건물의 높이와 놓을 다리의 개수이다.

입력의 끝은 -1 하나만 있는 줄로 표시된다.

각 입력 줄마다 두 줄을 출력한다. 첫 번째 줄에는 이동한 계단 수의 최소 총합을 정수로 출력한다. 두 번째 줄에는 다리를 놓을 층 번호를 오름차순으로 출력한다. 지상층은 0으로 나타내며, 높이가 x인 건물의 가장 높은 층은 x − 1이다.