Vacation

Interview

Time limit5sMemory limit64 MB

Summary

From a start city on a line with a fixed day budget where each move or city visit costs one day, pick the contiguous block with the most attractions.

Level: Medium5 of 10
Topics: Two pointers, Prefix sum, Array
Solved: No attempts yet

Problem

Jianjia is planning a vacation in Taiwan. $n$ cities lie along one highway, numbered $0$ through $n-1$ . City $i$ is adjacent only to $i-1$ and $i+1$ , except the endpoints, which have one neighbor.

City $i$ has $a_i$ attractions. Jianjia has $d$ vacation days and chooses a starting city before the trip begins. Each day, exactly one of these actions is allowed.

Move to an adjacent city.
Visit every attraction in the current city that has not been visited yet.

Attractions in a city are never counted twice. Find the maximum number of distinct attractions Jianjia can visit.

Input

Line 1: $n$ , starting city $start$ , and vacation length $d$
Line 2: $a_0$ through $a_{n-1}$ , the attraction counts in order

Output

Print the maximum number of attractions that can be visited.

Examples3

Example 1
Input
```
5 2 7
10 2 20 30 1
```
Expected output
```
60
```
Example 2
Input
```
1 0 1
5
```
Expected output
```
5
```
Example 3
Input
```
3 1 3
1 100 1
```
Expected output
```
101
```