假定有一个无限长的数轴，数轴上每个坐标上的数都是0。

现在，我们首先进行 n 次操作，每次操作将某一位置x上的数加c。

接下来，进行 m 次询问，每个询问包含两个整数l和r，你需要求出在区间[l, r]之间的所有数的和。

输入格式
第一行包含两个整数n和m。

接下来 n 行，每行包含两个整数x和c。

再接下里 m 行，每行包含两个整数l和r。

输出格式
共m行，每行输出一个询问中所求的区间内数字和。

数据范围
−109≤x≤109 ,
1≤n,m≤105 ,
−109≤l≤r≤109 ,
−10000≤c≤10000
输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例：
8
0
5

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+5;
const int INF=0x3f3f3f3f;
struct node{
    int num,val;
}no[N];
bool opter(node a,node b){
    return a.num<b.num;
}
int n,m,sum[N];
int findl(int x){
    int l=1,r=n+1;
    while(l<r){
        int mid=l+r>>1;
        if(no[mid].num>=x){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    return l;
}
int findr(int x){
    int l=0,r=n;
    while(l<r){
        int mid=(l+r+1)>>1;

        if(no[mid].num<=x){
            l=mid;
        }else{
            r=mid-1;
        }
    }
    return l;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>no[i].num>>no[i].val;
    }
    //按坐标位置从小到大排序
    sort(no+1,no+n+1,opter);

    int j=1;
    for(int i=2;i<=n;i++){
        //当没有重复时不变，有重复时将后面的加到前面，
        //到下一个不重复时，将下一个的往前挪
        if(no[i].num>no[i-1].num){
            j++;
            no[j]=no[i];
        }else{
            no[j].val+=no[i].val;
        }
    }
    n=j;
    no[0].num=-INF;
    no[n+1].num=INF;
    //前缀和
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+no[i].val;
    }
    int l,r;
    for(int i=0;i<m;i++){
        cin>>l>>r;
        int mi=findl(l);
        int ma=findr(r);
        cout<<sum[ma]-sum[mi-1]<<endl;
    }
    return 0;
}