Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0100 - THE URGE TO MERGE

   The Acme Consulting Group has sent you into a new technology park to enhance dynamism, synergy and sustainability. You’re not sure what any of these terms mean, but you’re pretty good at making money, which is what you plan on doing. The park consists of a 3 × n grid of facilities. Each facility houses a start-up with an inherent value.        By  facilitating  mergers  between  neighboring  start-ups,  you intend to increase their value, thereby allowing you to fulfill your life-long dream of opening your own chain  of  latte-and-burrito  shops.

   Due to anti-trust laws, any individual merger may only involve two start-ups and no start-up may be involved in more than one merger. Furthermore, two start-ups may only merge if they are housed in adjacent facilities (diagonal doesn’t count). The added value generated by a merger is equal to the product of the values of the two start-ups involved. You may opt to not involve a given start-up in any merger, in which case no added value is generated. Your goal is to find a set of mergers with the largest total added value generated. For example, the startup values shown in the figure on the left, could be optimally merged as shown in the figure on the right for a total added value of 171.

Input

   The first line of each test case will contain a single positive integer n 1000 indicating the width of the facilities grid. This is followed by three lines, each containing n positive integers (all 100) representing the values of each start-up. A line containing a single 0 will terminate input.

Output

   For each test case, output the maximum added value attainable via mergers for that set of start-ups.

Examples

stdin

stdout

1

4

7

2

4

9

3

5

9

3

9

5

1

8

0

 

 

 

Case 1: 171


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2014-01-26
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.NA East Central 2013.H

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.