20553번 - 다오와 디지니의 데이트

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

버블힐은 직선 형태로 연결된 $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$)

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