휴가

지안지아는 타이완 휴가를 계획하고 있다. $n$개의 도시가 하나의 고속도로를 따라 $0$부터 $n-1$까지 번호가 붙어 있다. 도시 $i$의 이웃은 $i-1$과 $i+1$뿐이며, 끝 도시는 한쪽 이웃만 갖는다.

도시 $i$에는 관광지가 $a_i$개 있다. 지안지아는 $d$일 동안 휴가를내며, 시작 도시를 미리 정한다. 하루에 할 수 있는 일은 둘 중 하나뿐이다.

• 인접한 도시로 이동한다.
• 현재 도시에 남아 있는 관광지를 모두 방문한다.

같은 도시의 관광지는 한 번 방문하면 다시 세지 않는다. 서로 다른 관광지를 최대한 많이 방문하도록 돕고, 그 최대 개수를 구하라.

• 1행: $n$, 시작 도시 번호 $start$, 휴가 일수 $d$
• 2행: $a_0$부터 $a_{n-1}$까지 공백으로 구분된 관광지 개수

방문할 수 있는 관광지의 최대 개수를 출력한다.