시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB152158945237.355%

문제

싫은데요 햄스터는 콩쥐를 위해서 깨진 독을 자기 몸으로 막으려고 한다.

햄스터는 유체라 자기 몸을 그림처럼 늘릴 수 있다.

또, 햄스터는 유체라 자기 몸을 아래 그림처럼 늘릴 수도 있다.

하지만 햄스터의 부피는 $M$으로 정해져 있기 때문에, 늘릴 수 있는 크기에는 한계가 있다.

독에 왼쪽부터 $N$개의 구멍이 일렬로 뚫려 있고, $i$번째 구멍의 크기 $A_i$가 주어진다. 햄스터는 구멍을 막기 위해 정확히 그 크기만큼의 부피를 소모해야 한다.

싫은데요 햄스터는 콩쥐에게 최대한 도움이 되길 원하기 때문에 자기 부피를 가능한 한 많이 활용하길 원한다.

어떻게 막으면 햄스터가 원하는 방식으로 독을 막는지 구해서 알려주자.

아무리 햄스터가 유체라고 하지만 몸을 둘로 나눌 수는 없기 때문에 막는 모든 구멍은 연속되어야 한다.

입력

입력은 아래와 같이 주어진다.

$N$ $M$

$A_1$ $A_2$ ... $A_N$

출력

구멍을 막는 데에 활용할 수 있는 최대 부피를 출력한다.

제한

  • $1\leq N\leq 500\,000$
  • $1\leq M\leq 10^9$
  • $1\leq A_i\leq 10^9$

예제 입력 1

8 10
2 2 2 2 11 2 5 2

예제 출력 1

9

$6$번째 구멍부터 $8$번째 구멍까지 막으면 총 $9$의 부피를 소모하고, 최대값인 $9$를 출력한다