== include(page="template/taskheader" task_id="sudest") ==

Fermierul Ion detine un teren de forma patrata, impartit in NxN patrate de latura unitate, pe care cultiva cartofi. Pentru recoltarea cartofilor fermierul foloseate un robot special proiectat in acest scop. Robotul porneste din patratul din stanga sus, de coordonate (1,1) si trebuie sa ajunga in patratul din dreapta jos, de coordonate (N, N). Traseul robotului este programat prin memorarea unor comenzi pe o cartela magnetica. Fiecare comanda specifica directia de deplasare (sud sau est) si  numarul de patrate pe care le parcurge in directia respectiva. Robotul strange recolta doar din patratele in care se opreste intre doua comenzi.
Din pacate, cartela pe care se afla programul s-a deteriorat si unitatea de citire a robotului nu mai poate distinge directia de deplasare, ci numai numarul de pasi pe care trebuie sa-i facă robotul la fiecare comanda. Fermierul Ion trebuie sa introduca manual, pentru fiecare comanda, directia de deplasare.

Fermierul Ion detine un teren de forma patrata, impartit in NxN patrate de latura unitate, pe care cultiva cartofi. Pentru recoltarea cartofilor fermierul foloseate un robot special proiectat in acest scop. Robotul porneste din patratul din stanga sus, de coordonate (1,1) si trebuie sa ajunga in patratul din dreapta jos, de coordonate (N, N). Traseul robotului este programat prin memorarea unor comenzi pe o cartela magnetica. Fiecare comanda specifica directia de deplasare (sud sau est) si  numarul de patrate pe care le parcurge in directia respectiva. Robotul strange recolta doar din patratele in care se opreste intre doua comenzi. Din pacate, cartela pe care se afla programul s-a deteriorat si unitatea de citire a robotului nu mai poate distinge directia de deplasare, ci numai numarul de pasi pe care trebuie sa-i faca robotul la fiecare comanda. Fermierul Ion trebuie sa introduca manual, pentru fiecare comanda, directia de deplasare.
h2. Cerinta
 
Scrieti un program care sa determine cantitatea maxima de cartofi pe care o poate culege robotul, in ipoteza in care Ion specifica manual, pentru fiecare comanda, directia urmata de robot. Se va determina si traseul pe care se obtine la recolta maxima.

h2. Date de intrare

...

Fisierul de intrare  sudest.in are urmatoarea structura:
Pe linia 1 se afla  numarul natural N, reprezentand  dimensiunea parcelei de teren.
Pe urmatoarele N linii se afla cate N numere naturale, separate prin spatii, reprezentand cantitatea de cartofi din fiecare patrat unitate.
Pe linia N+2 se afla un numar natural K reprezentand numarul de comenzi aflate pe cartela magnetica.
Pe linia N+3 se afla K numerele naturale C1, …,CK, separate prin spaaii, reprezentand numarul de pasi pe care trebuie sa-i efectueze robotul la fiecare comanda.
 

h2. Date de iesire