Card Game (Easy)

Interview

Time limit1sMemory limit1024 MB

Summary

Given sorted attack values and H hit points, find the most cards you can attack with before the opponent dies, or -1 if they never die.

Level: Easy3 of 10
Topics: Greedy, Prefix sum, Sorting
Solved: No attempts yet

Problem

You are playing a card game.

The opponent has $H$ hit points, and you have $N$ cards with various attack values. When you attack with a card, the opponent's hit points decrease by that card's attack value. When hit points become $0$ or less, the opponent dies.

You want to kill the opponent as late as possible, so you try to kill them using as many cards as possible. Given the attack values in ascending order, find the maximum number of cards you can use. Each card can be used only once.

Input

The first line contains the number of cards $N$ and the opponent's hit points $H$ , separated by a space.

The second line contains the attack values $d_i$ of the $N$ cards in ascending order, separated by spaces.

All input values are integers.

Output

On the first line, print the maximum number of cards you can use to kill the opponent.

If you cannot kill the opponent even after using all the cards, print $-1$ .

Constraints

$1 \leq N, H \leq 1\,000\,000$
$1 \leq d_i \leq 1\,000\,000$

Examples2

Example 1
Input
```
4 5
1 2 4 5
```
Expected output
```
3
```
Example 2
Input
```
4 15
1 2 4 5
```
Expected output
```
-1
```