E - はじめての動的計画法(Easy Dynamic Programming)

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

狐のジャップルさんは, 日々 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_2a_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.

入力

x

出力

与えられた入力が, 問題 " Do use Dynamic Programming " の正しい出力となるような, 問題 " Do use Dynamic Programming " の入力を 1 つ作り出力せよ.


入力例 1

11

出力例 1

4 4
1
1
2
3

Story: kagamiz
Problem: kagamiz
Tester: kyuridenamida