用字典代替a数组和前缀和s数组
注释掉的是用list实现对比字典实现

def find(x):
    l,r = 0,len(all)-1

    while l < r:
        mid  = (l+r)//2
        if all[mid] >= x: r = mid
        else: l = mid+1

    return r + 1


if __name__ == "__main__":
    n,m = map(int,input().split())

    # a,s = [0]*(100000),[0]*(100000)
    a,s = {0:0},{0:0}
    all,add, query= [], [],[]

    for i in range(n):
        x,c = map(int,input().split())

        add.append((x,c))

        all.append(x)

    for i in range(m):
        l,r = map(int,input().split())

        query.append((l,r))

        all.append(l)
        all.append(r)


    #排序去重
    all = list(set(sorted(all)))

    #插入操作
    for x, c in add:
        x2 = find(x)
        if x2 not in a:
            a[x2] = c
        else: 
            a[x2] += c

    # for x, c in add:
    #     x2 = find(x)
    #     a[x2] += c

    #处理前缀和
    for i in range(1,len(all)+1):
        if i not in a:
            a[i]=0
        s[i] = s[i-1] + a[i]

    #for i in range(1,len(all)+1):
    # 
    #     s[i] = s[i-1] + a[i]

    #处理询问
    for l,r in query:
        l,r= find(l),find(r)
        print(s[r]-s[l-1])