問題文

狐のジャップルさんは, 日々 K4PC (Kool code for Programming Contest) に出題する問題を考えています.

今日, 彼はこのような問題を思いつきました.

Do use Dynamic Programming

問題文

スーパーの生鮮食品コーナーには N 本の胡瓜が売られています. レジで会計をするときに, 生鮮食品コーナーで買った胡瓜の重さの合計が W 以下だと, 生産者のミカミさん直筆のサインが貰えます.

ケンスケくんはミカミさんの作る胡瓜が大好きなので, 出来るだけ多くのサインが欲しいです. ケンスケくんの為に, ミカミさんからサインを貰う方法の個数を求めて挙げて下さい.

課題

N 個の荷物があって, それぞれの荷物には正整数の重さ a_i (1 ≦ i ≦ N) が付いている.

重さの和が W 以下となるような荷物の集合の個数を求めよ.

---

制約

• 1 ≦ N ≦ 1000.
• 1 ≦ W ≦ 1000.
• 1 ≦ a_i ≦ 1000.

---

入力

N W
a_1
a_2
…
a_N

出力

問題の解を 1 行に出力せよ.

---

入力例 1

4 4
1
1
2
3

出力例 1

11

\{\},\ \{a_1\},\ \{a_2\},\ \{a_3\},\ \{a_4\},\ \{a_1,\ a_2\},\ \{a_1,\ a_3\},\ \{a_2,\ a_3\},\ \{a_1,\ a_4\},\ \{a_2,\ a_4\},\ \{a_1,\ a_2,\ a_3\} が条件を満たす荷物の集合である.

ジャップルさんはこの問題が簡単過ぎる気がしてきたため, 次のような問題を思いつきました.

課題

問題 " Do use Dynamic Programming " (問題文を参照) の入力であって, 答えが x となるようなものを 1 つ出力せよ.

制約

すべての入力データは以下の制約を満たす．

• 1 ≦ x ≦ 10^{18}.

この制約条件のもとで，条件を満たすような答が存在することが保証されている．(13:51 追記)

また，この問題には部分点が設定されており，2 点分の入力データは追加で以下の制約を満たす．

• x ≦ 1000.

入力例 1

11

出力例 1

4 4
1
1
2
3