시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 115 44 39 60.000%

문제

크레이지 파크의 버블힐에도 새해가 찾아왔다. 다오와 디지니는 새해가 된 기념으로 데이트를 하며 버블힐의 곳곳을 둘러보려고 한다.

버블힐은 직선 형태로 연결된 $N$개의 장소로 구성되어 있다. 버블힐에는 두 장소를 잇는 길이 $N-1$개 있는데, 1 이상 $N-1$ 이하의 각 정수 $i$에 대해 $i$번 장소와 $i+1$번 장소가 길로 연결되어 있다.

다오와 디지니는 데이트 계획을 분 단위로 꼼꼼하게 세우려고 한다. 다오와 디지니는 매 분마다 다음의 세 가지 행동 중 하나를 선택하여 하려고 한다.

  • $2 \leq i \leq N$을 만족하는 $i$번 장소에 있을 경우, 길을 이용하여 $i-1$번 장소로 이동한다.
  • $1 \leq i \leq N-1$을 만족하는 $i$번 장소에 있을 경우, 길을 이용하여 $i+1$번 장소로 이동한다.
  • 현재 위치한 장소에 그대로 머문다.

다오와 디지니는 매 분, 1분 전에 위치했던 장소 $i$와 현재 위치한 장소 $j$에 따라 행복도를 얻는다. $i \neq j$일 경우, 다오와 디지니는 $h_j$만큼의 행복도를 얻을 수 있다. $h_j$가 음수일 수도 있는데, 이 경우 $-h_j$만큼의 행복도를 잃는다는 뜻이다. 만약 $i=j$라면, 다오와 디지니의 행복도 변화는 0이다.

데이트에 쓸 수 있는 시간이 $T$분밖에 남지 않았기 때문에, 마을에서 출발하여 행복도를 가장 크게 만든 후 돌아오려고 한다. 즉, 처음과 끝 위치는 항상 다오와 디지니가 사는 1번 마을이 되어야 한다. 다오와 디지니가 얻을 행복도를 구해 주자.

입력

첫 줄에 두 정수 $N$과 $T$가 주어진다. ($2 \le N \le 100\,000$, $1 \le T \le 10^{9}$)

두 번째 줄에 $N$개의 정수가 공백으로 구분되어 주어지며, $i$번째 수는 $h_i$를 의미한다. ($-10^9 \le h_i \le 10^9$, $h_1 = 0$)

출력

다오와 디지니가 이번 데이트에서 얻을 수 있는 행복도의 최댓값을 출력한다.

예제 입력 1

5 6
0 6 -2 9 3

예제 출력 1

18

예제 입력 2

5 11
0 6 -2 9 3

예제 출력 2

41

출처

High School > 경기과학고등학교 > 나는코더다 2020 송년대회 B번