sudest

Fermierul Ion deţine un teren de formă pătrată, împărţit în $N \times N$ pătrate de latură unitate, pe care cultivă cartofi. Pentru recoltarea cartofilor fermierul foloseşte un robot special proiectat în acest scop. Robotul porneşte din pătratul din stânga sus, de coordonate $(1,1)$ şi trebuie să ajungă în pătratul din dreapta jos, de coordonate $(N,N)$. Traseul robotului este programat prin memorarea unor comenzi pe o cartelă magnetică. Fiecare comandă specifică direcţia de deplasare (sud sau est) şi numărul de pătrate pe care le parcurge în direcţia respectivă. Robotul strânge recolta doar din pătratele în care se opreşte între două comenzi.

Din păcate, cartela pe care se află programul s-a deteriorat şi unitatea de citire a robotului nu mai poate distinge direcţia de deplasare, ci numai numărul de paşi pe care trebuie să-i facă robotul la fiecare comandă. Fermierul Ion trebuie să introducă manual, pentru fiecare comandă, direcţia de deplasare.

Cerință

Scrieţi un program care să determine cantitatea maximă de cartofi pe care o poate culege robotul, în ipoteza în care Ion specifică manual, pentru fiecare comandă, direcţia urmată de robot. Se va determina şi traseul pe care se obţine la recolta maximă.

Date de intrare

Fişierul de intrare sudest.in are următoarea structură:

• Pe linia $1$ se află numărul natural $N$, reprezentând dimensiunea parcelei de teren.
• Pe următoarele $N$ linii se află câte $N$ numere naturale, separate prin spaţii, reprezentând cantitatea de cartofi din fiecare pătrat unitate.
• Pe linia $N+2$ se află un număr natural $K$ reprezentând numărul de comenzi aflate pe cartela magnetică.
• Pe linia $N+3$ se află $K$ numerele naturale $C_1,\dots,C_K$, separate prin spaţii, reprezentând numărul de paşi pe care trebuie să-i efectueze robotul la fiecare comandă.

Date de ieșire

Fişierul de ieșire sudest.out va conţine pe prima linie cantitatea maximă de cartofi recoltată de robot. Pe următoarele $K+1$ linii vor fi scrise, în ordine, coordonatele pătratelor unitate ce constituie traseul pentru care se obţine cantitate maximă de cartofi, câte un pătrat unitate pe o linie. Coordonatele scrise pe aceeaşi linie vor fi separate printr-un spaţiu. Primul pătrat de pe traseu va avea coordonatele 1 1, iar ultimul va avea coordonatele N N. Dacă sunt mai multe trasee pe care se obţine o cantitate maximă de cartofi recoltată se va afişa unul dintre acestea.

Restricții și precizări

• $5 \leq N \leq 100$;
• $2 \leq K \leq 2 \cdot N - 2$;
• $1 \leq C_1, \dots, C_k \leq 10$;
• Cantitatea de cartofi dintr-un pătrat de teren este număr natural între $0$ şi $100$;
• Pentru fiecare set de date de intrare se garantează că există cel puţin un traseu;
• Se consideră că robotul strânge recolta şi din pătratul de plecare $(1,1)$ şi din cel de sosire $(N,N)$;
• Pentru determinarea corectă a cantităţii maxime recoltate se acordă $50\%$ din punctajul alocat testului respectiv; pentru cantitate maximă recoltată şi traseu corect se acordă $100\%$.

Exemplu

sudest.in

6
1 2 1 0 4 1
1 3 3 5 1 1
2 2 1 2 1 10
4 5 3 9 2 6
1 1 3 2 0 1
10 2 4 6 5 10
5
2 2 1 4 1

sudest.out

29
1 1
3 1
5 1
6 1
6 5
6 6

Explicație

Un alt traseu posibil este:

1 1
1 3
1 5
2 5
6 5
6 6

dar costul său este $1+1+4+1+5+10=22$.