You are given two arrays A and B each of size N. You have to make K moves in total. In each move, you can remove either the first element or the last element of any one of the arrays. In next move also, you can do the same, not considering the elements removed in previous moves. The points earned for each move is equal to the value of the element removed. Your goal is to maximize the total points earned after K moves.
Input Format
The first line of the input contains two space separated Integers N and K .
The second line contains N space separated integers A1A2...AN .
The third line contains N space separated integers B1B2...BN .
Constraints
- 1≤N≤103
- 1≤K≤2N
- −109≤Ai≤109
- −109≤Bi≤109
Output Format
Print a single integer denoting the maximum value of total points earned after K moves.
Let the first array be A and second array be B.
In the 1st move the last element of array A is removed. Therefore after the 1st move A=[1,2,3,4] B=[0,2,3,4,5] points earned = 5
In the 2nd move the last element of array B is removed. Therefore after the 2nd move A=[1,2,3,4] B=[0,2,3,4] points earned = 5 + 5 = 10
In the 3rd move the last element of array A is removed. Therefore after the 3rd move A=[1,2,3] B=[0,2,3,4] points earned = 10 + 4 =14
In the 4th move the last element of array B is removed. Therefore after the 4th move A=[1,2,3] B=[0,2,3] points earned = 14 + 4 =18
In the 5th move the last element of array A is removed. Therefore after the 5th move A=[1,2] B=[0,2,3] points earned = 18 + 3 = 21
In the 6th move the last element of array B is removed. Therefore after the 6th move A=[1,2] B=[0,2] points earned = 21 + 3 = 24
Therefore, maximum total points earned after 6 moves = 24
