Plocka Äpplen
IOI 2015 avgörs i Almaty, som ungefär betyder "äpplets fader". Olga bor i Almaty, och har en äppelodling med två rader träd. På varje rad finns det $N$ träd. Varje träd har ett visst antal mogna äpplen.
Olga börjar besöka trädet i det sydvästra hörnet (det längst till vänster på den undre raden), och plockar alla dessa äpplen. Sedan går hon till ett av de närmsta träden (i norr, öster, väster eller syd) och plockar dess äpplen.
Din uppgift är att beräkna, givet hur många äpplen som är på de olika träden, hur många äpplen Olga sammanlagt kan plocka om hon totalt hinner plocka äpplena från högst $K$ träd.
Indata
Den första raden innehåller heltalen $N$ och $K$, separerade med ett blanksteg.
Nästa rad innehåller $N$ heltal - antalet äpplen på träden i den norra raden, listade från trädet längst till väst till det längst till öst.
Den tredje och sista raden innehåller också $N$ heltal - antalet äpplen på träden i den södra raden.
Utdata
Ditt program ska skriva ut ett heltal - antalet äpplen Olga hinner plocka.
Förklaring av exempel
I exemplet hinner hon bara plocka äpplena från två träd. Trädet hon börjar på har $6$ äpplen. Trädet till norr har $7$ äpplen, medan trädet direkt till öst bara har $4$ äpplen. Hon hinner därför som mest plocka $6 + 7 = 13$ äpplen.
Poängsättning
Gränserna i alla testfall är $1 \le N \le 15$ och $1 \le K \le 15$. Antalet äpplen på varje träd är mellan $0$ och $1000$.
-
I testfall värda 50 poäng har alla träd lika många äpplen.
-
I testfall värda ytterligare 50 poäng kan det finnas olika antal äpplen på olika träd.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 2 7 3 6 4 |
13 |
