/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は遠足に持っていくおやつを選んでいます。お店には N 種類のおやつがあり、おやつ i（1 \le i \le N）の値段は 1 個あたり P_i 円です。どの種類のおやつも十分な個数が売られています。
高橋君は、N 種類のおやつの中から好きな種類を選び、選んだ種類のおやつをそれぞれちょうど T 個ずつ買います。選ばなかった種類のおやつは 1 個も買いません。
おやつの購入に使える金額は合計で E 円以下です。この予算の範囲内でおやつの種類を選ぶとき、最大で何種類のおやつを買うことができるでしょうか。
すなわち、買う種類の集合 S \subseteq \{1, 2, \ldots, N\} を選び、\displaystyle \sum_{i \in S} P_i \times T \le E を満たすときの |S| の最大値を求めてください。
制約
- 1 \leq N \leq 10^5
- 1 \leq T \leq 10^4
- 1 \leq E \leq 10^{14}
- 1 \leq P_i \leq 10^9
- 入力はすべて整数
入力
N T E P_1 P_2 \ldots P_N
- 1 行目には、おやつの種類数を表す整数 N、各種類を買う個数を表す整数 T（個）、予算を表す整数 E（円）が、スペース区切りで与えられる。
- 2 行目には、各おやつの 1 個あたりの値段を表す整数 P_1, P_2, \ldots, P_N（円）が、スペース区切りで与えられる。
出力
買うことができるおやつの種類数の最大値を 1 行で出力せよ。
入力例 1
5 2 20 3 5 1 4 7
出力例 1
3
入力例 2
8 3 100 10 20 5 15 8 30 12 25
出力例 2
3
入力例 3
10 10000 100000000000000 1000000000 999999999 999999998 999999997 999999996 999999995 999999994 999999993 999999992 999999991
出力例 3
10
Score : 300 pts
Problem Statement
Takahashi is choosing snacks to bring on a field trip. The store has N types of snacks, and snack i (1 \le i \le N) costs P_i yen per piece. Each type of snack is available in sufficient quantity.
Takahashi selects some types from the N types of snacks, and buys exactly T pieces of each selected type. He does not buy any pieces of the types he did not select.
The total amount spent on snacks must be at most E yen. Within this budget, what is the maximum number of types of snacks he can buy?
In other words, find the maximum value of |S| when choosing a set S \subseteq \{1, 2, \ldots, N\} of types to buy such that \displaystyle \sum_{i \in S} P_i \times T \le E.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq T \leq 10^4
- 1 \leq E \leq 10^{14}
- 1 \leq P_i \leq 10^9
- All inputs are integers
Input
N T E P_1 P_2 \ldots P_N
- The first line contains an integer N representing the number of types of snacks, an integer T (pieces) representing the number of pieces to buy of each selected type, and an integer E (yen) representing the budget, separated by spaces.
- The second line contains integers P_1, P_2, \ldots, P_N (yen) representing the price per piece of each snack, separated by spaces.
Output
Print the maximum number of types of snacks that can be bought, in a single line.
Sample Input 1
5 2 20 3 5 1 4 7
Sample Output 1
3
Sample Input 2
8 3 100 10 20 5 15 8 30 12 25
Sample Output 2
3
Sample Input 3
10 10000 100000000000000 1000000000 999999999 999999998 999999997 999999996 999999995 999999994 999999993 999999992 999999991
Sample Output 3
10