分数: 300 分
问题陈述
Takahashi is choosing snacks to bring on a field trip. The store has N 零食种类及零食 i (1 \le i \le N) costs P_i 每件日元。 Each type of snack is available in sufficient quantity.
Takahashi selects some types from the N 零食种类,买的正好 每个选定类型的 T 件。 He does not buy any pieces of the types he did not select.
The total amount spent on snacks must be at most E 日元。 Within this budget, what is the maximum number of types of snacks he can buy?
In other words, find the maximum value of |S| 选择套装时 S \subseteq \{1, 2, \ldots, N\} 购买的类型 \displaystyle \sum_{i \in S} P_i \times T \le E.
约束
- 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
- 第一行包含一个整数 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.
- 第二行包含整数 P_1, P_2, \ldots, P_N (yen) representing the price per piece of each snack, separated by spaces.
输出
Print the maximum number of types of snacks that can be bought, in a single line.
示例输入 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