The Urge to Merge

The Acme Consulting Group has sent you into a new technology park to raise its dynamism, synergy and sustainability. You are not sure what any of those words mean, but you are good at making money, and making money is what you plan to do.

The park is a $3 \times n$ grid of facilities. Each facility houses one start-up, and every start-up has a value of its own. Arranging mergers between neighboring start-ups raises that value, which is how you will finally pay for the chain of latte-and-burrito shops you have always wanted to open.

Anti-trust law allows only two start-ups in a single merger, and no start-up may take part in more than one merger. Two start-ups may merge only when their facilities are adjacent, and facilities that touch at a corner are not adjacent. The added value of a merger is the product of the values of the two start-ups in it. You may leave a start-up out of every merger, and then it adds nothing.

Find the set of mergers with the largest total added value. For the grid in the first example the best choice of mergers adds up to 171.

The input holds several test cases.

The first line of a test case is the width $n$ ($1 \le n \le 1000$) of the facility grid. Three lines follow, each with $n$ integers, giving the values of the start-ups in that row. Every value is between $1$ and $100$.

A line holding a single $0$ ends the input.

For each test case print one line in the form Case i: v, where $i$ is the test case number counting from $1$ and $v$ is the largest total added value the mergers can reach.