Two Decks

Interview

Time limit1sMemory limit1024 MB

Summary

Wonbin removes at most K items from the top or bottom of two stacks to minimize the weight of the heavier backpack he is left carrying.

Level: Medium5 of 10
Topics: Prefix sum, Brute force, Array
Solved: No attempts yet

Problem

Seunghyeong and Wonbin prepared two backpacks for a trip. Each backpack holds $N$ items.

The first backpack has items with weights $A_1, A_2, \dots, A_N$ stacked from bottom to top. $A_N$ is the weight of the item on top.
The second backpack has items with weights $B_1, B_2, \dots, B_N$ stacked from bottom to top. $B_N$ is the weight of the item on top.

The weight of a backpack is the sum of the weights of the items left inside it. Wonbin can perform at most $K$ operations. In each operation, he picks one of the two backpacks and removes the item on the top or the bottom of it. The chosen backpack's weight drops by the weight of the removed item.

After Wonbin finishes, Seunghyeong decides which backpack to carry. Being shrewd, he always carries the lighter of the two. If the two weights are equal, he carries either one. Wonbin must carry the backpack that Seunghyeong does not choose.

Find the minimum possible weight of the backpack Wonbin has to carry.

Input

The first line contains two integers $N$ and $K$ ( $1 \leq N \leq 5\,000$ , $0 \leq K \leq N$ ).

The second line contains $N$ integers $A_1, A_2, \dots, A_N$ ( $1 \leq A_i \leq 10^9$ ), the item weights in the first backpack.

The third line contains $N$ integers $B_1, B_2, \dots, B_N$ ( $1 \leq B_i \leq 10^9$ ), the item weights in the second backpack.

Output

Print the minimum possible weight of the backpack that Wonbin has to carry.

Examples2

Example 1
Input
```
3 2
3 1 4
1 5 9
```
Expected output
```
6
```
Example 2
Input
```
3 0
3 1 4
1 5 9
```
Expected output
```
15
```