题目描述

你需要维护一个序列 $a_1,\dots,a_n$ 。

给定一个操作序列 $(x_1,y_1),\dots,(x_n,y_n)$ ，操作 $(x,y)$ 表示将 $a_1,\dots,a_x$ 的值加上 $y$ 。

共 $m$ 次查询，每次查询给出 $l,r$ ，问对初始值为 $0$ 的序列 $a$ 依次执行操作 $(x_l,y_l),\dots,(x_r,y_r)$ ，最后 \mathop\max\limits_{i=1}^n a_i 的值。

输入格式

第一行两个整数 $n,m$ （$1\le n,m\le 5\times 10^5$）；

接下来 $n$ 行每行两个整数 $x_i,y_i$（$1\le x_i\le n, |y_i|\le n$）；

接下来 $m$ 行，每行两个整数 $l,r$（$1\le l\le r\le n$）。

输出格式

输出 $m$ 行，每行一个整数，表示每次查询的答案。

6 5
6 4
2 6
5 -5
3 6
1 2
3 6
1 6
1 6
2 6
2 6
5 6

19
19
15
15
8

题目使用协议

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）。

以下『本仓库』皆指 THUPC2024 官方仓库（https://gitlink.org.cn/thusaa/thupc2024final）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。