특별한 서빙

면접 대비

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

요약

앞에서부터 x_i를 누적할 때 합이 M 이상이 되지 않도록, 가지를 받는 학생 수의 최소를 구합니다.

문제

???: 가지라니, 비슷하지도 않잖아요...

NLCS Jeju에서는 파묻튀(파마산을 묻혀 튀긴 소고기)를 서빙하는 것을 좋아한다.

그러나 학생들은 파묻튀보다 신선한 가지를 먹고 싶어 한다!

급식실에 $N$ 명의 학생이 차례로 서 있다. 줄의 앞에서부터 $i$ 번째 학생이 가지 대신 파묻튀를 받으면 불만도가 $x_i$ 만큼 늘어나고, 가지를 받으면 불만도가 $x_i$ 만큼 줄어든다. 불만도의 초깃값은 $0$ 이다.

음식을 앞에 서 있는 학생부터 순서대로 서빙할 때, 어느 순간이라도 불만도가 $M$ 이상이 되면 학생들은 '가지 운동'을 일으킨다.

가지 운동을 일으키지 않게 하기 위한 가지의 최소 개수를 구하는 프로그램을 작성하시오.

첫 번째 줄에 $N$ 과 $M$ 이 공백으로 구분되어 주어진다.

두 번째 줄에 $x_i$ 를 나타내는 $N$ 개의 정수가 공백으로 구분되어 주어진다.

첫 번째 줄에 학생들이 가지 운동을 일으키지 않게 하기 위한 가지의 최소 개수를 출력한다.