配点 : 点
アイスティーを愛飲しているTくんは、アイスティー屋さんにやってきました。
アイスティー屋さんでは 種類のアイスティーが横一列に並べて売られており、それぞれのアイスティーには から の番号が付けられた全 種類の茶葉のうちどれか 種類の茶葉が使用されています。
左から 番目のアイスティーの値段は 円で、使用されている茶葉の種類は です。
見栄っ張りのTくんは、「ここからここまで全部買います」と言いアイスティーを購入することにしました。具体的には、以下のように購入します。
Tくんは、購入するアイスティーの値段の合計が 円以下になるかつ、全 種類の茶葉それぞれについて購入するアイスティーのうち少なくとも つに使用されているようにしたいです。
アイスティーの購入方法は全部で 通り考えられますが、そのうちTくんの希望を満たすようなものは何通りありますか?
入力は以下の形式で標準入力から与えられます。
答えを出力してください。
5 2 14 3 7 2 10 2 1 2 1 2 1
6
Tくんの希望を満たす購入方法は の つです。
購入するアイスティーの値段の合計はそれぞれ 円で、確かに全て 円以下です。
これ以外に希望を満たす購入方法はありません。例えば、 という購入方法は値段の合計は 円ですが、茶葉 を使用しているアイスティーが無いので希望を満たしません。
4 1 8 2 2 2 2 1 1 1 1
10
全ての購入方法が希望を満たします。
2 2 10 3 5 1 1
0
どのように購入しても全ての茶葉が揃わない場合もあります。