题目描述

农场的有一个用于科学研究的大棚，大棚内有一条笔直的直线，直线的每个整数位置上都种植了一株科研植物，整数位置的范围为 $[0,10^9]$ 。

大棚内设有一个自动灌溉机，会根据各植物检测到的特征数据，对特定位置的植物进行灌溉 。

现从计算机中调取了某一天 $N$ 次灌溉记录。第 $i$ 条灌溉记录有两个数据 $P_i$ 和 $X_i$ ，代表为位于 $P_i$ 位置的植物，灌溉了 $X_i$ 毫升的水。

针对当天的灌溉记录有 $M$ 次询问，第 $j$ 条询问需要计算一个区间 $[L_j,R_j]$ 当天的总灌溉量。

请编程计算出 $M$ 次询问，每次的询问结果。

输入

第 $1$ 行读入 $2$ 个整数 $N$ 和 $M$ ；

接下来 $N$ 行，每行读入 $2$ 个整数 $P$ 和 $X$ ；

接下来 $M$ 行，每行读入 $2$ 个整数 $L$ 和 $R$ ；

输出

输出 $M$ 行，每行一个整数，代表每次询问的结果。

样例

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

1
4
5
6

说明

数据范围

对于 $100$ 的数据， $1 \le N,M \le 10^5$ ， $0 \le P \le 10^9$ ， $1 \le X \le 10^4$ ， $0 \le L \le R \le 10^9$ ；