配点: 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 整数中。