/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君は小学校の先生です。今日はクラスのお楽しみ会で、子どもたちにお菓子を配ることになりました。
クラスには N 人の子どもがいて、子ども i (1 \leq i \leq N) はちょうど S_i 個のお菓子をもらうと満足します。S_i 個より少ない場合は満足しません。
高橋君が持っているお菓子は全部で P 個です。高橋君は N 人の子どもの中から、お菓子を渡す子どもの集合を選びます。選ばれた子ども i にはちょうど S_i 個のお菓子を渡し、選ばれなかった子どもにはお菓子を渡しません。ただし、渡すお菓子の合計が P 個を超えてはなりません。なお、誰にも渡さないことや、お菓子が余ることも許されます。
お菓子を受け取った子どもは必ず満足し、お菓子を受け取らなかった子どもは満足しません。お菓子を渡す子どもの集合をうまく選ぶことで、満足する子どもの人数を最大化してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq P \leq 10^{18}
- 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数
入力
N P S_1 S_2 \ldots S_N
- 1 行目には、子どもの人数を表す整数 N と、高橋君が持っているお菓子の総数を表す整数 P が、スペース区切りで与えられる。
- 2 行目には、各子どもが満足するために必要なお菓子の個数を表す整数 S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。
出力
満足する子どもの最大人数を 1 行で出力せよ。
入力例 1
5 10 3 1 4 2 5
出力例 1
4
入力例 2
7 20 5 3 8 2 6 1 4
出力例 2
5
入力例 3
10 1000000000000 500000000 100000000 300000000 200000000 400000000 150000000 250000000 50000000 350000000 450000000
出力例 3
10
Score : 333 pts
Problem Statement
Takahashi is an elementary school teacher. Today is the class fun party, and he needs to distribute sweets to the children.
There are N children in the class, and child i (1 \leq i \leq N) is satisfied if they receive exactly S_i sweets. They will not be satisfied if they receive fewer than S_i sweets.
Takahashi has a total of P sweets. He will choose a subset of the N children to give sweets to. Each chosen child i receives exactly S_i sweets, and children not chosen receive no sweets. However, the total number of sweets given out must not exceed P. It is allowed to choose no children at all, and it is also allowed for sweets to be left over.
Children who receive sweets are always satisfied, and children who do not receive sweets are not satisfied. By choosing the subset of children to give sweets to wisely, maximize the number of satisfied children.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq P \leq 10^{18}
- 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
- All inputs are integers.
Input
N P S_1 S_2 \ldots S_N
- The first line contains an integer N representing the number of children and an integer P representing the total number of sweets Takahashi has, separated by a space.
- The second line contains integers S_1, S_2, \ldots, S_N representing the number of sweets each child needs to be satisfied, separated by spaces.
Output
Print the maximum number of satisfied children on a single line.
Sample Input 1
5 10 3 1 4 2 5
Sample Output 1
4
Sample Input 2
7 20 5 3 8 2 6 1 4
Sample Output 2
5
Sample Input 3
10 1000000000000 500000000 100000000 300000000 200000000 400000000 150000000 250000000 50000000 350000000 450000000
Sample Output 3
10