사과 따기

이 문제는 사과 따기 문제의 학교 예선용 버전이다. 채점 방식은 학교 예선과 같고, 테스트 케이스 수가 훨씬 적다.

IOI 2015는 알마티에서 열린다. 알마티는 대략 "사과의 아버지"라는 뜻이다. 올가는 알마티에 살면서 두 줄의 나무가 있는 사과 과수원을 가지고 있다. 각 줄에는 나무가 $N$그루 있다. 나무마다 익은 사과가 일정 개수 달려 있다.

올가는 남서쪽 모퉁이에 있는 나무(아래쪽 줄의 가장 왼쪽 나무)부터 방문하여 그 나무의 사과를 모두 딴다. 그런 다음 바로 옆 나무(북쪽, 동쪽, 서쪽, 남쪽) 중 하나로 이동하여 그 나무의 사과를 딴다.

각 나무에 달린 사과의 개수가 주어질 때, 올가가 최대 $K$그루의 나무에서 사과를 따고 시간이 다 된다면 사과를 모두 몇 개 딸 수 있는지 구하는 것이 목표이다.

첫째 줄에는 정수 $N$과 $K$가 공백으로 구분되어 주어진다.

다음 줄에는 위쪽 줄에 있는 나무의 사과 개수 $N$개가 서쪽 나무부터 동쪽 나무 순서대로 주어진다.

셋째 줄이자 마지막 줄에도 아래쪽 줄에 있는 나무의 사과 개수 $N$개가 같은 순서로 주어진다.

올가가 딸 수 있는 사과 개수를 정수 하나로 출력한다.

모든 테스트 케이스에서 $1 \le N \le 15$이고 $1 \le K \le 15$이다. 각 나무의 사과 개수는 $0$에서 $1000$ 사이이다.

예시에서 올가는 나무 두 그루의 사과만 딸 수 있다. 시작하는 나무에는 사과가 $6$개 있다. 북쪽 나무에는 $7$개가 있고, 바로 동쪽 나무에는 $4$개밖에 없다. 따라서 올가는 최대 $6 + 7 = 13$개의 사과를 딸 수 있다.