페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4028

제3회 디미고 프로그래밍 챌린지 오픈 콘테스트

두루마리 휴지 1초 1024MB

문제

장난꾸러기 강산이 신희찬의 노트북에 음료수를 쏟았다 강산은 디미고의 특별한 두루마리 휴지를 최대한 효율적으로 신희찬에게 가져다주어야 한다.

디미고의 두루마리 휴지는 1번부터 N번까지 N개의 휴지로 구성되어 있으며, 각 휴지는 흡수력 s_i를 가지고 있다. 휴지 중에는 물에 젖어있는 휴지가 있을 수 있는데, 이 경우 흡수력은 음수다. 강산은 정수 K(1≤K≤N)를 골라, 1번부터 K번까지의 휴지를 선택하려고 한다. 선택한 휴지들 중에서 사용할 휴지를 마음대로 고를 수 있고, 사용하지 않는 휴지는 버리게 된다.

사용하는 휴지의 흡수력 합이 T 이상이 되도록 휴지를 고르는 방법 중 사용하는 휴지의 수와 버리는 휴지의 수 중 더 큰 값의 최솟값을 구하시오.


입력

첫 번째 줄에 N과 T가 공백으로 구분하여 주어진다. (1≤N≤10^5,1≤T≤10^{15})

두 번째 줄에 s_1,s_2,⋯,s_N이 공백으로 구분하여 주어진다. (−10^{10}≤s_i≤10^{10})

주어지는 모든 수는 정수다.


출력

첫 번째 줄에 문제의 정답을 출력한다. 만약, 흡수력이 T이상이 되도록 하는 방법이 없다면 −1을 출력한다.


예제 #1

5 7
3 -2 4 1 2
2

예제 #2

6 6
-1 1 2 -2 2 -2
-1
로그인해야 코드를 작성할 수 있어요.