D - Ice Tea


配点 :
  

問題文


アイスティーを愛飲しているTくんは、アイスティー屋さんにやってきました。

アイスティー屋さんでは 種類のアイスティーが横一列に並べて売られており、それぞれのアイスティーには から の番号が付けられた全 種類の茶葉のうちどれか 種類の茶葉が使用されています。

左から 番目のアイスティーの値段は 円で、使用されている茶葉の種類は です。

見栄っ張りのTくんは、「ここからここまで全部買います」と言いアイスティーを購入することにしました。具体的には、以下のように購入します。

  • 整数の組 を定め、左から 番目のアイスティーを全て つずつ購入する。

Tくんは、購入するアイスティーの値段の合計が 円以下になるかつ、全 種類の茶葉それぞれについて購入するアイスティーのうち少なくとも つに使用されているようにしたいです。

アイスティーの購入方法は全部で 通り考えられますが、そのうちTくんの希望を満たすようなものは何通りありますか?

  

制約


  • 入力は全て整数   

入力


入力は以下の形式で標準入力から与えられます。



  

出力


答えを出力してください。

  

入力例1


5 2 14
3 7 2 10 2
1 2 1 2 1

出力例1


6

Tくんの希望を満たす購入方法は つです。

購入するアイスティーの値段の合計はそれぞれ 円で、確かに全て 円以下です。

これ以外に希望を満たす購入方法はありません。例えば、 という購入方法は値段の合計は 円ですが、茶葉 を使用しているアイスティーが無いので希望を満たしません。

入力例2


4 1 8
2 2 2 2
1 1 1 1

出力例2


10

全ての購入方法が希望を満たします。

入力例3


2 2 10
3 5
1 1

出力例3


0

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

提出


Go (1.14)