만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

카드 게임 (Easy)

면접 대비

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

요약
오름차순으로 주어진 카드 N장의 공격력과 상대의 체력 H가 주어질 때, 상대가 죽기 전까지 쓸 수 있는 카드의 최대 개수를 구합니다. 모든 카드를 써도 죽지 않으면 -1입니다.
난이도

쉬움10점 중 3점

유형
그리디, 누적 합, 정렬
정답자
아직 제출이 없습니다

문제

당신은 카드 게임을 하고 있다.

상대의 체력은 HH이고, 당신은 공격력이 제각각인 카드를 총 NN개 가지고 있다. 카드를 사용해 공격하면 상대의 체력이 그 카드의 공격력만큼 줄어든다. 체력이 00 이하가 되면 상대는 죽는다.

당신은 상대를 최대한 늦게 죽이고 싶다. 그래서 가능한 한 많은 카드를 사용해 상대를 죽이려고 한다. 카드의 공격력이 오름차순으로 주어질 때, 최대 몇 개의 카드를 사용할 수 있는지 구하여라. 각 카드는 한 번만 사용할 수 있다.

입력

첫 번째 줄에 카드의 수 NN과 상대의 체력 HH가 공백으로 구분되어 주어진다.

두 번째 줄에 NN개 카드의 공격력 did_i가 오름차순으로 공백으로 구분되어 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

첫 번째 줄에 상대를 죽이기 위해 사용할 수 있는 카드의 최대 개수를 출력하여라.

모든 카드를 사용해도 상대를 죽일 수 없다면 −1-1을 출력하여라.

제한

  • 1≤N,H≤1 000 0001 \leq N, H \leq 1\,000\,000
  • 1≤di≤1 000 0001 \leq d_i \leq 1\,000\,000

예제2

  1. 예제 1

    입력
    4 5
    1 2 4 5
    
    예상 출력
    3
    
  2. 예제 2

    입력
    4 15
    1 2 4 5
    
    예상 출력
    -1