#17 麻布株式会社

難易度

# 問題 2020年、麻布株式会社は負債$K$億円を抱えていた。 これを脱却するには、それぞれ価値$A_i$億円の$N$件の物件から、適当な数物件を売却しなければならない。 ただし、価値の高さを問わずに、できるだけ資産は残したいので、売却する物件数は最小にしたい。何件物件を売却すればいいかを求めよ。また、$K$億円の借金を返済できない場合は$-1$を出力せよ。 # 入力 1行目には、麻布株式会社が持っている物件の数$N$と現在抱えている負債$K$(億円単位)が空白区切りで与えられる。 2行目には、$N$個の物件のそれぞれの資産価値$A_i$(億円単位)が空白区切りで与えられる。 # 出力 $K$億円の負債を返済するために売却しなければならない物件の最小数を1行で出力せよ。 # 制約 - $1 \leq N \leq 10^5$ - $1 \leq K \leq 10^{18}$ - $1 \leq A_i \leq 10^{18} (1≤i≤N)$ - 入力される数は全て整数である - 価値$J$の物件を売却した時に得られる資金は$J$である。 # 入出力例 ## 入出力例1 ### 入力 ``` 3 2 1 1 3 ``` ### 出力 ``` 1 ``` - 3つ目の物件を売却すると、3億円の資金を回収することができ、負債を返済できます。 ## 入出力例2 ### 入力 ``` 1 500000000000 100 ``` ### 出力 ``` -1 ``` - 5千京円を返済する手段はありません。倒産あるのみ。