← 返回题目列表

AtCoder · awc0026_c

C. 实地考察零食

中文机器翻译题面 查看原题

分数: 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