Pick Apples

Time limit2sMemory limit1024 MB

Summary

Given two rows of N trees with apple counts, find the maximum apples Olga can collect starting from the bottom-left tree and walking to at most K distinct trees on the 2 by N grid.

Level: Medium4 of 10
Topics: Brute force, DFS, Implementation, Backtracking
Solved: No attempts yet

Problem

This is the school qualifier version of the Pick Apples problem. Scoring works as in the school qualifier, and the number of test cases is much smaller.

IOI 2015 is held in Almaty, which roughly means "father of apples". Olga lives in Almaty and owns an apple orchard with two rows of trees. Each row has $N$ trees. Each tree holds a certain number of ripe apples.

Olga starts at the tree in the southwest corner (the leftmost tree in the bottom row) and picks all of its apples. She then moves to one of the neighboring trees (north, east, west, or south) and picks its apples.

Given the number of apples on each tree, your task is to compute the total number of apples Olga can pick if she has time to pick apples from at most $K$ trees.

Input

The first line contains the integers $N$ and $K$ , separated by a space.

The next line contains $N$ integers, the number of apples on the trees in the top row, listed from the westernmost tree to the easternmost tree.

The third and final line also contains $N$ integers, the number of apples on the trees in the bottom row.

Output

Your program must print one integer, the number of apples Olga can pick.

Constraints

In all test cases, $1 \le N \le 15$ and $1 \le K \le 15$ . Each tree has between $0$ and $1000$ apples.

Hint

In the example, she can only pick apples from two trees. The tree she starts on has $6$ apples. The tree to the north has $7$ apples, while the tree directly to the east has only $4$ apples. She can therefore pick at most $6 + 7 = 13$ apples.

Examples1

Example 1
Input
```
2 2
7 3
6 4
```
Expected output
```
13
```