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 ≤ 105
- 1 ≤ candies[i] ≤ 104
- 1 ≤ k ≤ n
Scoring
- For 60% of total score, 1 ≤ n ≤ 100
- For 100% of total score, original constraints
Here, k = 3 so you need to choose 3 boxes.
After the first step, the number of candies you have will always be 1. However, choosing the box from the end first will maximize your total candies. The optimal strategy is to take the three boxes on the right, giving you 1 + 6 + 5 = 12 candies.
