寻找宝藏

Problem Description

你得到了一张藏宝图，这上面标记了埋藏在地底下的 $n$ 个海盗藏宝箱，编号依次为 $1$ 到 $n$，第 $i$ 个宝箱的坐标是 $(i,p_i)$，打开它你将得到 $v_i$ 枚金币。 你现在位于 $(0,0)$，每次你可以选择从 $(x,y)$ 移动到 $(x+1,y)$ 或者 $(x,y+1)$，当你位于某个宝箱正上方时，你将可以挖出它并拿走里面的所有金币。 不幸的是，有一个危险的陷阱区域没有被标记出来！通过多方调研，你得知这是一个边平行坐标轴的矩形区域，它是 $m$ 种可能的位置分布之一。请对于每种可能的情况分别计算按照最优路线你能拿走多少金币。 假设陷阱区域的位置分布是第 $i$ 种可能，假设它是以 $(x_1,y_1)$ 和 $(x_2,y_2)$ 为对顶点的矩形，那么 $(x,y)$ 是陷阱当且仅当 $x_1\leq x\leq x_2$ 且 $y_1\leq y\leq y_2$。你的路线不能途径任何陷阱点。当然，你只需要考虑当前的第 $i$ 个矩形，不需要考虑其它 $m-1$ 个矩形。

Input

第一行包含一个正整数 $T$ ($1\leq T\leq 100$)，表示测试数据的组数。 每组数据第一行包含两个正整数 $n,m$ ($1\leq n,m\leq 300\,000$)，分别表示宝箱的数量以及可能的矩形数。 接下来 $n$ 行，第 $i$ 行包含两个正整数 $p_i,v_i$ ($1\leq p_i\leq n$, $1\leq v_i\leq 10^9$)，依次描述每个宝箱。输入数据保证 $p_i$ 互不相同。 接下来 $m$ 行，每行四个正整数 $x_1,y_1,x_2,y_2$ ($1\leq x_1\leq x_2\leq n$, $1\leq y_1\leq y_2\leq n$)，依次描述每种可能的矩形陷阱区域。 输入数据保证 $\sum n\leq 1\,500\,000$，且 $\sum m\leq 1\,500\,000$。

Output

对于每组数据输出 $m$ 行，其中第 $i$ 行输出一个整数，即在危险陷阱区域是第 $i$ 个矩形的情况下你最多能拿走的金币数量。

Sample Input

1
3 5
2 4
3 3
1 5
1 1 1 1
1 1 1 3
2 1 3 3
1 1 3 2
1 1 3 3

Sample Output

7
5
4
3
0

Source

2024“钉耙编程”中国大学生算法设计超级联赛（4）