특별한 서빙

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

요약

파묻튀를 받으면 불만도가 x_i만큼 오르고 가지를 받으면 x_i만큼 내려간다. 불만도가 언제나 M 미만이 되도록 가지를 줘야 하는 학생 수의 최솟값을 구한다.

문제

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

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

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

급식실에 $N$ 명의 학생들이 차례로 서 있다. 줄의 앞에서부터 $i$ 번째 학생이 가지 대신 파묻튀를 받았을 경우 $x\_i$ 만큼 불만도가 늘어나고, 가지를 받았을 경우에는 $x\_i$ 만큼 불만도가 내려간다. 단, 불만도의 초깃값은 $0$ 이다.

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

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

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

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

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