There are n boxes arranged in a row. Each box contains some candies. You are given an array candies which tell you the number of candies in each box.
In one step, you can choose a box from the beginning or from the end of the row, and take all the candies in that box. You can choose exactly k boxes.
Given the integer array candies and the integer k, find the maximum number of candies you can get.
Input

First line contains n, the number of boxes
Next line contains n space seperated integers, denoting the elements of candies array
Last line contains the integer k

Output

Print a single integer, denoting the maximum number of candies you can get

Constraints

1 ≤ n ≤ 10⁵
1 ≤ candies[i] ≤ 10⁴
1 ≤ k ≤ n

Scoring

For 60% of total score, 1 ≤ n ≤ 100
For 100% of total score, original constraints