Mr. Krabs loves money. He enters a bank and sees that there are n rooms arranged in a row. The only rooms with doors are the two rooms on either corner. Initially, all the rooms are locked (including the corner ones). To enter a room, it must be unlocked with a key.
Mr. Krabs is able to steal k keys from the sleeping night guard. Each key can be used to unlock only one room. To reach one of the inner rooms, he has to unlock an adjacent room first.
Eg: If there are 5 rooms labelled: 1 2 3 4 5
Only Rooms 1 and 5 can be accessed initially. To unlock room 2, either room 1 or room 3 must be unlocked. Similarly to unlock Room 4, he must unlock room 5 or room 3 first.
Each room has some money in it. The money present in room i is given by A[i]. Using the k keys, calculate what is the maximum possible amount of money obtainable.

-----Input:-----
- First line will contain n, number of rooms.
- Second line will contain space separated integers, denoting A[i], money present in each room.
- Third line will contain an integer, k, the number of keys available.

-----Output:-----
Maximum money obtained.

-----Constraints-----
- 1 <= Number of Rooms <= 10^5
- 1 <= A[i] <= 10^4
- 1 <= k <= Number of Rooms

-----Subtasks-----
- 40 points : 1 <= Number of Rooms <= 100
- 60 points : Number of Rooms > 100

-----Sample Input:-----
7
1 2 3 4 5 6 1
3

-----Sample Output:-----
12

-----Explanation:-----
For the first step, Mr. Krabs can only unlock the room at the left corner or the right corner. If he unlocks the room in the right corner, he obtains 1 dollar. He can then go on to unlock the second last room and gain 6 dollars, for a total of 7 dollars. Finally he can unlock the third last room and get 5 dollars, for a total of 12 dollars.
This is the maximum amount of money he can get with only 3 keys.

见题面

见题面