싫은데요

면접 대비

시간 제한1초메모리 제한1024 MB

요약

양의 정수 N개로 이루어진 수열에서 연속된 구간의 합이 M을 넘지 않도록 하는 최댓값을 구합니다.

문제

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

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

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

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

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

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

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

아무리 햄스터가 유체라고 해도 몸을 둘로 나눌 수는 없으므로, 막는 구멍은 모두 연속되어야 한다.

$N$ $M$

$A\_1$ $A\_2$ ... $A\_N$

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