Gems

Vasilică lucrează la un nou joc şi deja a ajuns la nivelul 13! Acest nivel trebuie să fie mai special (având în vedere numărul lui). Până la acest nivel Gemini (personajul principal al jocului) a acumulat $N$ tipuri de pietre preţioase (gems), fiecare tip de piatră având o valoare cunoscută (fie $v_i$ valoarea pietrelor preţioase de tipul $i$, $1 \leq i \leq N$). La acest nivel pe ecran apar $P \cdot P$ camere, dispuse pe $P$ linii şi $P$ coloane sub forma unui tablou bidimensional. Camera de pe linia $i$ ($1 \leq i < P$) şi coloana $j$ ($1 \leq j \leq P$) are uşi care se deschid doar din această cameră, astfel:

• prima uşă permite trecerea în camera de pe linia $i+1$ şi coloana $j-1$ (dacă această cameră există, adică $j>1$);
• a doua uşă permite trecerea în camera de pe linia $i+1$ şi coloana $j$;
• a treia uşă permite trecerea în camera de pe linia $i+1$ şi coloana $j+1$ (dacă această cameră există, adică $j<P$).

Unele dintre camerele de pe linia $P$ (cea mai de jos) au uşă spre exterior (dacă Gemini ajunge în una dintre aceste camere poate trece la nivelul următor).

În fiecare cameră există o singură piatră preţioasă. Pietrele preţioase au fost distribuite în camere în ordinea tipurilor de la $1$ la $N$, parcurgând camerele în ordinea crescătoare a liniilor, iar pe aceeaşi linie în ordinea crescătoare a coloanelor; după plasarea într-o cameră a unei pietre de tipul $N$, se revine din nou la tipul $1$. De exemplu, dacă $N=5$, valorile pietrelor sunt $1,7,8,1,3$ şi $P=4$, distribuţia pietrelor preţioase în camere va fi:

În fiecare cameră e indicat tipul pietrei preţioase plasate în camera respectivă, iar în paranteză valoarea acesteia. Gemini trebuie să plece dintr-o cameră situată în partea de sus a ecranului (linia $1$) şi să ajungă într-o cameră de pe linia $P$ care are ieşire spre exterior, adunând pietre preţioase cu valoare totală cât mai mare.

Cerință

Să se scrie un program care, cunoscând numărul de tipuri de pietre preţioase $N$, valorile pietrelor preţioase $v_1, v_2, \dots, v_N$, numărul de camere de pe o linie/coloană $P$, precum şi camerele de pe linia $P$ care au ieşire spre exterior, determină valoarea totală maximă a pietrelor preţioase pe care Gemini le poate acumula atunci când trece la nivelul următor (în condiţiile din joc).

Date de intrare

Fişierul de intrare gems.in conţine pe prima linie numerele naturale $N$ şi $P$ cu semnificaţia din enunţ.

Pe cea de a doua linie se află $N$ numere naturale $v_1, v_2, \dots, v_N$ ($v_i$ fiind valoarea pietrelor preţioase de tipul $i$, $1 \leq i \leq N$).

Pe ultima linie se află numere naturale distincte cuprinse între $1$ şi $P$ reprezentând coloanele pe care se află camerele de pe linia $P$ care au uşă spre exterior.

Valorile scrise pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieșire

Fişierul de ieşire gems.out va conţine o singură linie pe care va fi scris un număr natural reprezentând răspunsul la cerinţa din enunţ.

Restricții și precizări

• $2 \leq N \leq 500$
• $0 \leq v_i \leq 200$, pentru $1 \leq i \leq N$
• $2 \leq P \leq 8 \ 000$

Exemplu

gems.in

5 4
1 7 8 1 3
2 4

gems.out

24

Explicație

Pietrele preţioase sunt distribuite ca în tabelul de mai sus.

Gemini va parcurge camerele $(1,3)$, $(2,4)$, $(3,4)$, $(4,4)$, acumulând pietre în valoare totală de $8+8+7+1=24$.