题目描述
给定两个长度为N的整数序列:A=(A1,A2,…,AN) 和 B=(B1,B2,…,BN)。
打印满足以下条件的整数对(l,r)的数量,其中 1≤l≤r≤N。
- min{Al,Al+1,…,Ar}+(Bl+Bl+1+⋯+Br)≤S
约束条件
- 1≤N≤2×105
- 0≤S≤3×1014
- 0≤Ai≤1014
- 0≤Bi≤109
- 输入中的所有值都是整数。
输入
输入以以下格式从标准输入给出:
N S
A1 A2 … AN
B1 B2 … BN
输出
打印答案。
示例输入1
示例输出1
以下六对整数(l,r)满足条件 1≤l≤r≤N 以及问题描述中的条件:(1,1), (1,2), (2,2), (2,3), (3,3) 和 (4,4)。
示例输入2
示例输出2