Sofa, So Good

한 소파 공방은 특별 제작 소파를 틀 짜기(framing) 와 그 다음 덮개 씌우기(upholstering) 의 두 단계로 만듭니다. 소파 한 세트의 주문이 들어오면, 작업자 수는 소파 수와 정확히 같고 모든 작업자가 작업에 참여합니다.

틀 짜기. 각 작업자가 각 소파의 틀을 짜는 데 걸리는 시간을 알고 있을 때, 관리팀은 각 작업자에게 소파를 정확히 하나씩 배정하되 틀 짜기 시간의 합이 최소가 되도록 배정합니다. 각 작업자는 소파를 하나만 틀 짭니다. 모든 작업자는 시각 0에 틀 짜기를 시작하므로, 소파의 틀을 짜는 데 t시간이 걸리는 작업자는 시각 t에 끝내고, 그 소파는 시각 t에 (틀 짜기가 끝나) 사용 가능해집니다.

덮개 씌우기. 이어서 관리팀은 각 작업자에게 덮개를 씌울 소파를 정확히 하나씩 배정합니다(자신이 틀을 짠 소파와 다를 수 있습니다). 작업자는 다음 두 조건이 모두 충족되어야 배정된 소파의 덮개 씌우기를 시작할 수 있습니다: 자신의 틀 짜기를 끝냈고, 배정된 소파의 틀 짜기가 끝났을 것. 따라서 작업자는 시각 max(자신의 틀 짜기 종료 시각, 배정된 소파의 틀 짜기 종료 시각)에 덮개 씌우기를 시작하고, 그 시각에 자신의 덮개 씌우기 시간을 더한 시각에 끝냅니다. 틀 짜기를 끝내고 덮개 씌우기를 시작하기 전까지 여유가 있는 작업자는 그 사이에 대기(유휴)합니다.

모든 작업자는 덮개 씌우기를 끝내는 즉시 퇴근하고 시각 0부터 현장에 있었으므로, 한 작업자의 현장 체류 시간은 그 작업자가 덮개 씌우기를 끝낸 시각과 같습니다. 위에서 정해진 틀 짜기 배정을 전제로, 관리팀은 모든 작업자의 현장 체류 시간의 합이 최소가 되도록 덮개 씌울 소파를 배정합니다. 각 주문에서 단계마다 최적의 작업자-소파 짝은 정확히 하나뿐입니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 소파의 수이자 작업자의 수인 양의 정수 n (n ≤ 50)으로 시작합니다. 이어지는 n개의 줄에는 각각 n개의 양의 정수가 있으며, j번째 줄의 i번째 값은 작업자 j가 소파 i의 틀을 짜는 데 걸리는 시간입니다(작업자와 소파는 1부터 번호가 매겨집니다). 그다음 n개의 줄은 같은 형식으로 덮개 씌우기 시간을 나타냅니다(j번째 줄의 i번째 값은 작업자 j가 소파 i의 덮개를 씌우는 데 걸리는 시간). 모든 시간은 1000 이하입니다. 0 하나만 있는 줄이 입력의 끝을 나타냅니다.

각 테스트 케이스마다 Case k: (k는 1부터 시작하는 테스트 케이스 번호)를 출력한 뒤, 작업자 1번부터 순서대로 작업자 한 명당 한 줄씩 n개의 줄을 출력합니다. 각 줄의 형식은 Worker w: f u t이며, f는 작업자 w가 틀을 짠 소파, u는 작업자 w가 덮개를 씌운 소파, t는 작업자 w가 덮개 씌우기를 끝낸 시각입니다(모든 작업자는 시각 0에 틀 짜기를 시작). 이 n개의 줄 뒤에 Total idle time: x를 출력하며, x는 각 작업자가 틀 짜기를 끝낸 뒤 덮개 씌우기를 시작하기 전까지 대기한 시간을 모든 작업자에 대해 합한 값입니다.