D - Ice Tea

配点 : 点
　　

アイスティーを愛飲している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

どのように購入しても全ての茶葉が揃わない場合もあります。