문제
지안지아는 타이완에서의 휴가를 계획하고 있다.
휴가동안 지안지아는 도시에서 도시로 이동하고 도시 안의 관광지들을 방문할 것이다.
타이완에는 하나의 고속도로를 따라서 n개의 도시들이 위치한다.
이 도시들은 순서대로 0부터 n−1까지의 번호가 붙어있다.
임의의 i (0<i<n−1)에 대해서, 도시 i의 인접한 도시는 도시 i−1과 i+1이다.
도시 0과 인접한 도시는 도시 1뿐이고, 도시 n−1과 인접한 도시는 도시 n−2뿐이다.
각 도시에는 여러 관광지들이 있다.
지안지아는 d일 동안의 휴가를 얻었고 가능한 많은 관광지들을 방문하고 싶다.
지안지아는 휴가를 시작할 도시를 선택했다.
휴가기간동안 매일 지안지아는 인접한 도시로 움직이거나 또는 현재 도시의 관광지들을 모두 방문한다.
그러나 두 행동을 하루에 모두 할수는 없다.
지안지아는 한 도시에 여러 번 머물더라도 같은 도시안의 관광지들을 결코 두 번 방문하지는 않는다.
지안지아가 가능한 많은 서로 다른 관광지들을 방문하도록 도와주자.
[예제]
지안지아는 7일의 휴가를 얻었고, (아래 표와 같이) 5개의 도시가 있고 도시 2에서 휴가를 시작하였다.
첫 번째 날 지안지아는 도시 2의 20개 관광지를 방문한다.
두 번째 날 지안지아는 도시 2에서 도시 3으로 이동하고 세 번째 날 도시 3의 30개 관광지들을 방문한다.
다음 3일동안 지안지아는 도시 3에서 도시 0으로 이동해서 일곱 번째 날에 도시 0의 10개 관광지들을 방문한다.
따라서지안지아가 방문한 관광지의 총 개수는 20 + 30 + 10 = 60이고
이것은 그가 도시 2에서 시작해서 7일 동안 방문할 수 있는 관광지들의 최대 개수이다.
도시 | 관광지 개수 |
0 | 10 |
1 | 2 |
2 | 20 |
3 | 30 |
4 | 1 |
일 | 행동 |
1 | 도시 2의 관광지들을 방문 |
2 | 도시 2에서 도시 3으로 이동 |
3 | 도시 3의 관광지들을 방문 |
4 | 도시 3에서 도시 2로 이동 |
5 | 도시 2에서 도시 1로 이동 |
6 | 도시 1에서 도시 0으로 이동 |
7 | 도시 0의 관광지들을 방문 |
지안지아가 방문할 수 있는 관광지들의 최대 개수를 계산하시오.
입력
첫째 줄에 도시의 개수 n, 시작 도시의 번호 start, 휴가일의 수 d가 주어진다. (2 ≤ n ≤ 100,000)
둘째 줄에는 도시 i의 관광지 개수가 0번 도시부터 순서대로 공백으로 구분해 주어진다.
한 도시 안의 관광지들의 최대 개수는 1,000,000,000보다 작거나 같은 음이 아닌 정수이다. 또, 0 ≤ d ≤ 2n + ⌊n/2⌋를 만족한다.
출력
예제1
527
10220301
60