← 返回题目列表

AtCoder · typical90_ay

051. 典型商店(★5)

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

配点: 5 点

問題文

在典型商店中有 N 种可区分的商品。商品有 1, 2, \cdots, N 编号,商品 i 的价格是 A_i 这是日元。

你从商店出售的商品中恰好选择 K 件,使价格总和为 P 我想购物,使总金额不超过...日元。可能的商品选择方式有几种呢?

此外,2 ...种商品的选择方式是,有某个商品 i 存在,并且商品 i 当一方被选中而另一方未被选中时被区分。

制約

  • 1 \leq K \leq N \leq 40
  • 1 \leq P \leq 10^{18}
  • 1 \leq A_i \leq 10^{16} (1 \leq i \leq N)
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N K P
A_1 A_2 \ldots A_N

出力

请打印答案。 到达


入力例 1

5 2 10
3 8 7 5 11

出力例 1

2

只是 执行 2 个商品被选中,总价格不超过... 10 日元的商品选择方式如下 2 是的。 请注意,我们正在寻找除以

  • 品物 1 和货物 请注意, 3 选择
  • 品物 1 和货物 请注意, 4 选择

入力例 2

5 1 10
7 7 7 7 7

出力例 2

5

请注意,即使是相同价格的商品也会被区分。


入力例 3

40 20 100
1 3 1 3 4 1 3 5 5 3 3 4 1 5 4 4 3 1 3 4 1 3 2 4 4 1 5 2 5 3 1 3 3 3 5 5 5 2 3 5

出力例 3

137846528820

答案是 也可能是 32 请注意,可能无法容纳在 bit 整数中。