24200번 - Plocka Äpplen 다국어

문제

Detta är skolkvalsvarianten av uppgiften Plocka Äpplen. Det innebär att poängsättningen sker som i skolkvalet och att antalet testfall är mycket färre.

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.

입력

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.

출력

Ditt program ska skriva ut ett heltal - antalet äpplen Olga hinner plocka.

제한

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 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.