题目描述

有 $n$ 张牌组成一个序列，每张牌用一个二元组 $(a_i, b_i)$ 表示，意味着打出这张牌需要消耗 $a_i$ 点费用，打出后可以获得 $b_i$ 点费用。

接下来你可以选择一个区间 $[l, r]$ 将这个区间中的卡取出来作为你的卡组。

开始时你的卡组会按照随机顺序排列并且你有 $E$ 点费用，然后你会依次从前往后打出这个排列中的卡。

当你打完这个排列中的卡后你的卡组又会重新随机排列然后你再依次打出，直到你无法再打出下一张牌（当前费用小于下一张牌需要消耗的费用）时停止。

如果一个卡组无论在什么情况下都能够无限打下去，我们则称这卡组可以「陀螺无限」。

现在求有多少个区间组成的卡组能够「陀螺无限」。

输入格式

第一行输入两个非负整数 $n, E$ 分别表示卡牌序列长度和初始能量值 $E\ (1 \leq n \leq 10^6, 0 \leq E \leq 10^9)$。

接下来一行 $n$ 个非负整数 $a_i\ (0 \leq a_i \leq 10^9)$ 表示每张卡牌打出需要消耗的能量。

接下来一行 $n$ 个非负整数 $b_i\ (0 \leq b_i \leq 10^9)$ 表示每张卡牌打出后能获得的能量。

输出格式

输出一行一个整数表示有多少个区间组成的卡组能够「陀螺无限」。

5 10
9 10 10 0 2
8 5 6 2 5

4

5 10
8 1 6 4 10
7 6 1 8 5

5

数据范围与提示

本题使用子任务捆绑测试。

对于 $100\%$ 的数据，$1 \leq n \leq 10^6$，$0 \leq E, a_i, b_i \leq 10^9$。

• Subtask 1（$20\%$）：$1 \leq n \leq 5000$
• Subtask 2（$10\%$）：$b_i \geq a_i$
• Subtask 3（$10\%$）：$E = 0$
• Subtask 4（$10\%$）：$0 \leq a_i, b_i \leq 1$
• Subtask 5（$20\%$）：$a_i \times b_i = 0$
• Subtask 6（$30\%$）：无特殊限制