Sofa, So Good

A sofa salon builds specialty sofas in two phases: framing and then upholstering. When an order for a set of sofas arrives, there are exactly as many workers as sofas, and every worker takes part.

Framing. Using the known time it takes each worker to frame each sofa, management assigns each worker exactly one sofa to frame, choosing the assignment that minimizes the sum of the framing times. Each worker frames only one sofa. All workers start framing at time 0, so a worker who takes t hours to frame their sofa finishes at time t, and that sofa becomes available (finished framing) at time t.

Upholstering. Management then assigns each worker exactly one sofa to upholster (possibly different from the sofa they framed). A worker can begin upholstering their assigned sofa only once both conditions hold: the worker has finished their own framing, and the assigned sofa has finished being framed. Therefore a worker's upholstering start time is s = max(own framing-finish time, assigned sofa's framing-finish time), and they finish upholstering at time s + (their upholstering time for that sofa). A worker who is free between finishing framing and starting upholstering waits (idle) during that gap.

Every worker leaves as soon as they finish upholstering, and all workers were present from time 0, so a worker's time on-site equals the time at which they finish upholstering. Given the framing assignment fixed above, management assigns the sofas to upholster so as to minimize the total on-site time summed over all workers. For each order there is exactly one optimal pairing of workers to sofas in each phase.

The input contains several test cases. Each test case starts with a positive integer n (n ≤ 50), the number of sofas, which equals the number of workers. The next n lines each contain n positive integers: the i-th value on the j-th line is the time it takes worker j to frame sofa i (workers and sofas are numbered from 1). The following n lines describe the upholstering times in the same format (the i-th value on the j-th line is the time worker j takes to upholster sofa i). All times are at most 1000. A line containing a single 0 terminates the input.

For each test case, print Case k: (k is the test-case number, starting at 1), followed by n lines, one per worker in order from worker 1. Each such line has the form Worker w: f u t, where f is the sofa worker w framed, u is the sofa worker w upholstered, and t is the time at which worker w finished upholstering (all workers start framing at time 0). After these n lines, print Total idle time: x, where x is the sum, over all workers, of the time each worker spent idle between finishing framing and starting upholstering.