Holiday Visit Optimization

Jianjia is planning his next holiday trip to Taiwan. Since he wants to visit as many tourist attractions as possible, he needs to carefully plan his daily activities. There are \(n\) cities in Taiwan arranged along a highway and numbered consecutively from \(0\) to \(n-1\). Jianjia has already decided the first city he will be in at the start of his holiday.

Every city has a certain number of attractions. Jianjia has a \(d\)-day holiday. On each day, he can choose exactly one action:

• Move to an adjacent city (i.e. from city \(i\) he can move to \(i-1\) or \(i+1\) if they exist), or
• Visit all the attractions in his current city.

If Jianjia revisits a city on another day, he will not gain additional attractions from that city because he visits the attractions only once. Note that the cities are arranged along a highway so that city \(0\) is only adjacent to city \(1\) and city \(n-1\) is only adjacent to city \(n-2\), while any city \(i\) with \(0 < i < n-1\) is adjacent to \(i-1\) and \(i+1\).

Your task is to help Jianjia plan his holiday itinerary so that he can visit the maximum total number of attractions. It is guaranteed that all movements and visits take exactly one day each. Jianjia starts at the chosen city (without having visited its attractions yet) on day 0. He must use these days wisely to move and visit.

Hint: Because the cities lie in a straight line, any optimal route will cover a contiguous block of cities that includes the starting city. If Jianjia chooses to visit all cities in a block from \(L\) to \(R\) (with \(L \leq s \leq R\) and \(s\) as the starting city), then he must use \((R - L + 1)\) days to visit the cities plus a certain number of days to move between them. The minimum number of move days required is given by:

[ \text{moves} = (s - L) + (R - s) + \min(s - L, R - s) ]

The total days needed is then:

[ \text{total_days} = (R - L + 1) + (s - L) + (R - s) + \min(s - L, R - s) ]

Your program should compute the maximum total attractions Jianjia can visit if he follows an optimal plan.

inputFormat

The first line contains three integers \(n\), \(d\), and \(s\): the number of cities, the number of days in the holiday, and the index of the starting city, respectively.

The second line contains \(n\) integers \(a_0, a_1, \ldots, a_{n-1}\), where \(a_i\) represents the number of attractions in city \(i\).

outputFormat

Output a single integer, the maximum total number of attractions that can be visited by following an optimal plan.

sample

5 7 2
1 3 2 5 4

11