Gigel a primit de la Moş Crăciun un joc. Jocul are o cutie formată din 2*N căsuţe, dispuse sub forma unei matrice cu două linii şi N coloane. În fiecare căsuţă poate fi plasat un singur jeton pe care este scris un număr întreg nenul din intervalul [-10, 10].
În figura de mai jos este ilustrată configuraţia unei cutii pentru N=7:
Unele dintre căsuţe pot rămâne goale şi nu este obligatoriu ca numărul de jetoane plasate în căsuţele de pe prima linie să fie acelaşi cu numărul de jetoane plasate în căsuţele de pe a doua linie.
Valoarea cutiei se calculează însumând produsele obţinute prin înmulţirea fiecărui număr de pe prima linie cu numărul corespunzător de pe cea de a doua linie (valoarea unei căsuţe goale fiind 0).
De exemplu, pentru cutia din figura de mai sus valoarea este:
6(=(-3)*(0) + (-1)*(-3) + (-2)*(2) + (0)*(4) + (5)*(0) +(-1)*(5) + (0)*(-2)).
Jetoanele pot fi mutate la stânga sau la dreapta pe linia lor din cutie respectând următoarele reguli:
1. la orice moment în orice căsuţă se află un singur jeton;
2. la orice moment ordinea jetoanelor de pe aceeaşi linie se păstrează.
Prin astfel de deplasări de jetoane se pot obţine diferite valori pentru cutie.
De exemplu făcând următoarele deplasări:
1. jetonul -1 de pe linia 1 coloana 6 este mutat în coloana 7
2. jetonul 5 de pe linia 1 coloana 5 este mutat în coloana 6
3. jetonul -3 de pe linia 2 coloana 2 este mutat în coloana 1
4. jetonul 4 de pe linia 2 coloana 4 este mutat în coloana 5
5. jetonul 2 de pe linia 2 coloana 3 este mutat în coloana 4
se obţine următoare amplasare a jetoanelor în cutie:
Valoarea cutiei în acest caz este 36=9+25+2 (şi este maximă posibil).
Scopul jocului este de a deplasa jetoanele din cutie astfel încât cutia să aibă o valoare cât mai mare.
Cerinţă
Scrieţi un program care determină valoarea maximă care se poate obţine pentru o configuraţie a cutiei dată, deplasând jetoanele din cutie după regulile de mai sus.
Date de intrare
Fişierul de intrare cutie2.in conţine pe numărul natural N, reprezentând numărul de coloane ale cutiei. Pe următoarele două linii este descrisă configuraţia cutiei. Pe fiecare dintre cele două linii sunt scrise N numere întregi separate prin spaţiu (0 semnificând o căsuţă goală, iar un număr nenul reprezentând numărul scris pe jetonul din căsuţă corespunzătoare).
Date de ieşire
Fişierul de ieşire cutie2.out va conţine o singură linie pe care va fi scrisă valoarea maximă care se poate obţine pentru configuraţia cutiei dată, deplasând jetoanele din cutie după regulile de mai sus.
