Skaitļu kaste sastāv no 2N nodalījumiem, kas izvietoti divās rindās un N kolonnās. Katrā nodalījumā var atrasties vesels skaitlis, kura absolūtā vērtība nav nulle un nepārsniedz 10.

Zīmējumā redzams viens kastes aizpildījums, ja N=7. Tukša rūtiņa nozīmē, ka attiecīgajā nodalījumā neatrodas neviens skaitlis. Aizpildīto nodalījumu skaits rindās var atšķirties.

Skaitļu kastes vērtību aprēķina sasummējot vienā kolonnā esošo skaitļu reizinājumus visās tajās kolonnās, kur aizpildīti abi nodalījumi. Iepriekš dotajā piemērā skaitļu kastes vērtība ir

-6 = (-1)*(-3) + (-2)*2 + (-1)*5 .

Pārvietojot katrā rindā dotos skaitļus pa labi un pa kreisi (bet nemainot to secību!), iespējams iegūt dažādas skaitļu kastes vērtības. Dotajā piemērā pirmajā rindā pārvietojot skaitļus 5 un -1 vienu nodalījumu pa labi, bet otrajā rindā skaitļus 2 un 4 vienu nodalījumu pa labi un -3 vienu nodalījumu pa kreisi, skaitļu kaste izskatīsies šādi:

Šīs skaitļu kastes vērtība ir 36 = (-3)*(-3) + 5*5 + (-1)*(-2).

Uzrakstiet programmu, kas noskaidro lielāko iespējamo dotās skaitļu kastes vērtību!

Izvaddatu pirmajā rindā dots naturāls skaitlis N (1≤N≤400) - skaitļu kastes kolonnu skaits. Faila otrajā rindā dots kastes pirmās rindas nodalījumu aizpildījums kā N veselu skaitļu virkne, kur katri divi blakus skaitļi atdalīti ar vienu tukšumsimbolu. i-tais skaitlis virknē atbilst skaitlim i-tajā šīs rindas kolonnā. Ja virknē dots skaitlis 0, tas nozīmē, ka atbilstošais nodalījums ir tukšs.

Faila trešajā rindā dota informācija par kastes otrās rindas aizpildījumu tādā pat formātā kā par kastes pirmās rindas aizpildījumu.

Ievaddatu vienīgajā rindā jāizvada vesels skaitlis - lielākā iespējamā skaitļu kastes vērtība.

Uzdevums izmantots Korejas informātikas olimpiādē 2003.gadā