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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'n = int(input())\nmoney = list(map(int, input().split()))\nk = int(input())\nf = len(money) - k\nans = curr = sum(money[:f])\nfor i in range(f, len(money)):\n    curr += money[i] - money[i - f]\n    ans = min(ans, curr)\nprint(sum(money) - ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13135