[GDKOI2024 提高组] 不休陀螺

赛事要求

2024 年广东省重点中学信息学邀请赛 (GDKOI 2024)

提高组 第二试

2024 年 1 月 7 日

注意事项

1. 严格按照题目所要求的格式进行输入、输出，否则严重影响得分。
2. 题目测试数据有严格的时间限制，超时不得分。
3. C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
4. 输入文件格式不用判错；输入输出文件名均已给定，不用键盘输入。
5. 评测环境为 NOI 系列活动标准竞赛环境，编译器版本为 g++ 9.4.0。
6. 若无特殊说明，结果的比较方式为全文比较 (过滤行末空格及文末回车)。
7. 对于 C++ 选手，64 位整数输入输出格式为 %lld。
8. 选手提交的程序源文件必须不大于 100KB。
9. 对于 C++ 语言的编译选项为 -O2 -std=c++14

题目描述

有 $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)$ 表示每张卡牌打出后能获得的能量。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

4

样例 #2

样例输入 #2

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

样例输出 #2

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%）：无特殊限制