D - Ice Tea

配点 : $500$ 点
　　

問題文

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

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

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

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

• 整数の組 $(l,r)(1 \leq l \leq r \leq N)$ を定め、左から $l,l+1, \ldots ,r$ 番目のアイスティーを全て $1$ つずつ購入する。

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

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

制約

• $1 \leq M \leq N \leq 400000$
• $1 \leq X \leq 10^9$
• $1 \leq A_i \leq 10^9$
• $1 \leq B_i \leq M$
• 入力は全て整数 　　

入力

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

出力

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

入力例1

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

出力例1

6

Tくんの希望を満たす購入方法は $(1,2),(1,3),(2,3),(3,4),(3,5),(4,5)$ の $6$ つです。

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

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

入力例2

4 1 8
2 2 2 2
1 1 1 1

出力例2

10

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

入力例3

2 2 10
3 5
1 1

出力例3

0

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